有一个长度为$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_bound 和 upper_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]);
}
}
|