目录

2020杭电多校第8场 B.Breaking Down News

目录
警告
本文最后更新于 2021-01-30,文中内容可能已过时。

有一个长度为$n$的数组$a$, 满足$a_i \in \{0, 1, 2\}$, 你要将其划分成一些连续的区间, 每个区间的长度在$[L, R]$之间, 每个区间的贡献是:

  • $-1$: 这个区间的和小于$0$
  • $0$: 这个区间的和等于$0$
  • $1$: 这个区间的和大于$0$

问最后总的贡献最大是多少

$1 \le L \le R \le n \le 10^6$

显然dp. 设$dp(i)$为前$i$个划分区间的最大贡献, 有

$$ dp(i) = \max_{L \le i-j \le R} \begin{cases} dp(j) + 1, & s_i - s_j > 0 \\ dp(j), & s_i - s_j = 0 \\ dp(j) - 1, & s_i - s_j < 0 \end{cases} $$

($s_i$ 表示$a_i$的前缀和)

朴素转移是$O(n^2)$的, 考虑优化.

限制了只能从前面的某段区间转移的dp是一类单调队列的题目, 但是这题由于转移方程不仅和 $s_j$ 有关, 还和 $s_i$ 有关, 所以普通的单调队列就不可行了.

这里的做法很巧妙, 既然转移和$s$有关, 那就构建一个以$s$为下标的权值线段树, 表示$s_i$对应的最大dp值. 如果$s_i > s_j$, 那么就查询$[mn, s_i-1]$中的最大值, 加上1; 如果$s_i < s_j$, 那么就查询$[s_i+1, mx]$, 减去1; 如果$s_i = s_j$, 那么就查询$[s_j, s_j]$. 三个值取max转移.

每次递推$i$的时候维护一下能够转移的区间, 每次增加右边一个, 减少左边一个, 要在线段树上更新这两个值.

那么问题来了, 可能一个$S$有多个$s_i$和他相等, 然后区间递推要更新线段树的时候, 怎么能够知道要更新成哪一个点的dp值? 或者说怎么能够知道某一点是否不在更新区间内?

Smile学长讲题的时候是说维护一个单调递减的队列, 我搞了半天没懂, 感觉要对每个$s_i$都开一个队列才可以, 就很迷.

然后查了一下题解, 找到一个神仙离散化的做法.

对$s_i$进行离散化, 但是sort以后不要unique. 让每一个相等的$s_i$对应不同的离散化的值, 也就是说, 对之前的下标做一个一一映射id, 使得$s[id] \le s[id+1]$.

例如

i 1 2 3 4 5 6 7 8 9...
s 3 2 3 3 1 2 1 1 2...

i  5 7 8 2 6 9 1 3 4...
s  1 1 1 2 2 2 3 3 3...
id 1 2 3 4 5 6 7 8 9...

然后对id开权值线段树, lower_boundupper_bound 查一下和$s_i$相等的id区间$[l, r)$, 然后分别从$[1, l-1]$, $[l, r)$, $[r, tot]$转移即可.

复杂度$O(n \log n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
const int MAXN = 1e6+10;

int t, n, L, R, tot;
int a[MAXN], c[MAXN], s[MAXN], dp[MAXN];
int id[MAXN];

struct Idx {
	int val, id;
	bool operator < (const Idx &I) const {
		return val < I.val;
	}
} b[MAXN];

struct Node {
	int l, r, mid, mx;
} tree[MAXN << 2];

void build(int u, int l, int r) {
	tree[u] = {l, r, (l+r) >> 1, -INTINF};
	if (l == r)
		return;
	build(LCH(u), l, tree[u].mid);
	build(RCH(u), tree[u].mid + 1,r);
}

void update(int u, int l, int x) {
	if (tree[u].l == tree[u].r)
		tree[u].mx = x;
	else {
		if (l <= tree[u].mid)
			update(LCH(u), l, x);
		else
			update(RCH(u), l, x);
		tree[u].mx = max(tree[LCH(u)].mx, tree[RCH(u)].mx);
	}
}

int query(int u, int l, int r) {
	if (tree[u].l == l && tree[u].r == r)
		return tree[u].mx;
	else if (r <= tree[u].mid)
		return query(LCH(u), l, r);
	else if (l > tree[u].mid)
		return query(RCH(u), l, r);
	else
		return max(query(LCH(u), l, tree[u].mid), query(RCH(u), tree[u].mid + 1, r));
}

int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d%d", &n, &L, &R);
		tot = 0;
		b[++tot] = {0, 0};
		for (int i = 1; i <= n; i++) {
			scanf("%d", a + i);
			s[i] = s[i - 1] + a[i];
			b[++tot] = {s[i], i};
		}
		sort(b+1,b+1+tot);
		for (int i = 1; i <= tot; i++)
			id[b[i].id] = i, c[i] = b[i].val;
		build(1, 1, tot);
		int ll=0, rr = -1, l, r;
		dp[0] = 0;
		for(int i = 1; i <= n; i++) {
			dp[i] = -INTINF;
			if(ll < i - R)
				update(1, id[ll], -INTINF), ll++;
			if(rr < i - L)
				++rr, update(1, id[rr], dp[rr]);
			l = lower_bound(c + 1, c + 1 + tot, s[i]) - c;
			r = upper_bound(c + 1, c + 1 + tot, s[i]) - c;
			if(r <= tot)
				dp[i] = max(dp[i], query(1, r,tot ) - 1);
			if(l < r)
				dp[i] = max(dp[i], query(1, l, r - 1));
			if(l > 1)
				dp[i] = max(dp[i], query(1, 1, l - 1) + 1);
		}
		printf("%d\n", dp[n]);
	}
}