[BZOJ 2006][NOI 2010] 超级钢琴

题目大意

给定一个长为 \(n\) 的序列,每个位置上有一个权值 \(a_i\),找出 \(k\) 个不同的长度在 \([l, r]\) 的区间,使得它们的和最大。

\(1 \leqslant n, \ k \leqslant 500,000\)

\(-1,000 \leqslant a_i \leqslant 1,000\)

题目链接

BZOJ 2006

CodeVS 1938

题解

当区间的右端点固定时,左端点有一个范围,在前缀和数组中找到这一段的最小值,就可以算出右端点固定时的一个满足条件的区间。用一个优先队列维护一个五元组 \((sum, v, l, r, k)\),其中五元组表示右端点为 \(v\),左端点为前缀和上区间 \([l, r]\) 内的第 \(k\) 小时的区间和为 \(sum\),五元组间的比较以 \(sum\) 为关键字。取出一个五元组后,插入其对应的 \(k + 1\) 的五元组。询问前缀和上的区间第\(k\)小用主席树。

代码

答案会超过 int

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <cstdio>
#include <queue>
#include <algorithm>
// #define DBG
const int MAXN = 500005;
struct PSegT {
struct Node {
int l, r;
Node *lc, *rc;
int cnt;
Node(int l, int r, Node *lc = NULL, Node *rc = NULL) : l(l), r(r), lc(lc), rc(rc), cnt((lc ? lc->cnt : 0) + (rc ? rc->cnt : 0)) {}
Node(int l, int r, int cnt) : l(l), r(r), cnt(cnt), lc(NULL), rc(NULL) {}
void pushDown() {
if (lc && rc) return;
int mid = l + (r - l) / 2;
if (!lc) lc = new Node(l, mid);
if (!rc) rc = new Node(mid + 1, r);
}
Node *insert(int val) {
if (val < l || val > r) return this;
if (val == l && val == r) return new Node(l, r, this->cnt + 1);
int mid = l + (r - l) / 2;
pushDown();
if (val <= mid) return new Node(l, r, lc->insert(val), rc);
else return new Node(l, r, lc, rc->insert(val));
}
int rank() {
return lc ? lc->cnt : 0;
}
} *roots[MAXN];
int n;
void build(int a[], int n) {
this->n = n;
roots[0] = new Node(0, n - 1);
for (int i = 1; i <= n; i++) {
roots[i] = roots[i - 1]->insert(a[i - 1]);
}
}
int query(int l, int r, int k) {
#ifdef DBG
printf("query in [%d, %d], k = %d\n", l, r, k);
#endif
Node *L = roots[l - 1], *R = roots[r];
int min = 0, max = n - 1;
while (min != max) {
L->pushDown();
R->pushDown();
int mid = min + (max - min) / 2, t = R->rank() - L->rank();
if (k <= t) L = L->lc, R = R->lc, max = mid;
else k -= t, L = L->rc, R = R->rc, min = mid + 1;
}
return min;
}
} pst;
int a[MAXN], sum[MAXN];
int map[MAXN];
void discretization(int n) {
std::copy(sum, sum + n, map + 1);
std::sort(map + 1, map + n + 1);
#ifdef DBG
for (int i = 1; i <= n; i++) printf("disc: map[%d] = %d, sum[%d] = %d\n", i, map[i], i - 1, sum[i - 1]);
#endif
int *end = std::unique(map + 1, map + n + 1);
for (int i = 1; i <= n; i++) sum[i - 1] = std::lower_bound(map + 1, end, sum[i - 1]) - map;
}
struct Data {
int sum, v, l, r, k;
bool operator<(const Data &another) const {
return sum < another.sum;
}
#ifdef DBG
void print() {
printf("Data : [sum: %d, v: %d, l: %d, r: %d, k: %d]\n", sum, v, l, r, k);
}
#endif
};
int main() {
int n, k, l, r;
scanf("%d %d %d %d", &n, &k, &l, &r);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];
discretization(n + 1);
pst.build(sum, n + 1);
std::priority_queue<Data> q;
q.push((Data) {map[sum[l]], l, 0, 0, 1});
for (int i = l + 1; i <= n; i++) {
int l2 = i - l;
int l1 = i - r;
if (l1 < 0) l1 = 0;
q.push((Data) {map[sum[i]] - map[pst.query(l1 + 1, l2 + 1, 1)], i, l1 + 1, l2 + 1, 1});
}
#ifdef DBG
printf("%d\n", sum[9]);
#endif
long long ans = 0;
for (int i = 1; i <= k; i++) {
Data t = q.top();
#ifdef DBG
t.print();
#endif
q.pop();
ans += t.sum;
if (t.r - t.l + 1 >= t.k + 1) q.push((Data) {map[sum[t.v]] - map[pst.query(t.l, t.r, t.k + 1)], t.v, t.l, t.r, t.k + 1});
}
printf("%lld\n", ans);
return 0;
}