题意描述
洛谷链接
小 Z 是一个小有名气的钢琴家，最近 C 博士送给了小 Z 一架超级钢琴，小 Z
希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出 \(n\)
个音符，编号为 \(1\) 至 \(n\)。第 \(i\) 个音符的美妙度为 \(A_i\)，其中 \(A_i\) 可正可负。
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于 \(L\) 且不多于 \(R\)。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
小 Z 决定创作一首由 \(k\)
个超级和弦组成的乐曲，为了使得乐曲更加动听，小 Z 要求该乐曲由 \(k\)
个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小
Z 想知道他能够创作出来的乐曲美妙度最大值是多少。
数据范围：\(-1000 \leq A_i \leq
1000\)，\(1 \leq L \leq R \leq
n\) 且保证一定存在满足要求的乐曲。
解题思路
由于各个超级和弦互不影响，我们可以考虑贪心地选取最大的几个超级和弦即为答案。
于是我们可以通过堆来维护最大的超级和弦。但由于 \(l, r\)
之间的范围过大，我们无法直接存储所有的超级和弦。
于是我们可以想到存储和弦的集合 \(S(i, l,
r)\)，表示这个超级和弦从 \(i\)
开始并在 \([l, r]\)
结束。对于每个集合赋予权值为集合内的美妙度最大值。于是我们可将集合放在堆中进行排序。每次从堆中取出后，假设最大美妙度的和弦为
\((i, t)\)，我们可以将这个集合拆分成
\(S(i, l, t - 1)\) 和 \(S(i, t + 1, r)\)
两个集合并插入堆中。这样就相当于删除了 \((i,
t)\) 这个和弦且不影响其他的和弦。像这样取出 \(k\) 个和弦即为答案。
对于和弦美妙度的计算，我们可以预处理前缀和，于是可得 \((l, r)\) 和弦的美妙度为 \(s_r - s_{l - 1}\)。在 \(S(i, l, r)\) 中取和弦的最大值只需计算 \(\max\limits_{j \in [l, r]} s_{j}\)
即可。这个过程需要使用 ST 表，我们只需预处理前缀和后对前缀和建立 ST
表即可。
时间复杂度为 \(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
| #include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
const int MAXN = 5e5;
const int LOG_MAXN = 19;
int n, k, l, r;
int a[MAXN + 1], s[MAXN + 1];
int f[MAXN + 1][LOG_MAXN + 1];
void prepare() {
for (int i = 1; i <= n; i++) f[i][0] = i;
int t = log(n) / log(2) + 1;
for (int j = 1; j < t; j++) {
for (int i = 1; i <= n - (1 << j) + 1; i++) {
if (s[f[i][j - 1]] > s[f[i + (1 << (j - 1))][j - 1]]) f[i][j] = f[i][j - 1];
else f[i][j] = f[i + (1 << (j - 1))][j - 1];
}
}
}
int query(int l, int r) {
int k = log(r - l + 1) / log(2);
if (s[f[l][k]] > s[f[r - (1 << k) + 1][k]]) return f[l][k];
else return f[r - (1 << k) + 1][k];
}
struct Node {
int i, l, r, t;
Node(int i, int l, int r) : i(i), l(l), r(r), t(query(l, r)) {}
bool operator<(const Node &o) const { return s[t] - s[i - 1] < s[o.t] - s[o.i - 1]; }
};
int main() {
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++) s[i] = s[i - 1] + a[i];
prepare();
std::priority_queue<Node> q;
for (int i = 1; i <= n - l + 1; i++) q.push(Node(i, i + l - 1, std::min(n, i + r - 1)));
long long ans = 0;
while (k--) {
Node u = q.top();
q.pop();
ans += s[u.t] - s[u.i - 1];
if (u.l <= u.t - 1) q.push(Node(u.i, u.l, u.t - 1));
if (u.t + 1 <= std::min(n, u.r)) q.push(Node(u.i, u.t + 1, std::min(n, u.r)));
}
printf("%lld\n", ans);
return 0;
}
|