NC17626. [NOI2010]超级钢琴
描述
小Z是一个小有名气的钢琴家，最近C博士送给了小Z一架超级钢琴，小Z希望能够用这架钢琴创作出世界上最美妙的音乐。
这架超级钢琴可以弹奏出n个音符，编号为1至n。第i个音符的美妙度为Ai，其中Ai可正可负。
一个“超级和弦”由若干个编号连续的音符组成，包含的音符个数不少于L且不多于R。我们定义超级和弦的美妙度为其包含的所有音符的美妙度之和。两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的。
小Z决定创作一首由k个超级和弦组成的乐曲，为了使得乐曲更加动听，小Z要求该乐曲由k个不同的超级和弦组成。我们定义一首乐曲的美妙度为其所包含的所有超级和弦的美妙度之和。小Z想知道他能够创作出来的乐曲美妙度最大值是多少。
输入描述
第一行包含四个正整数n, k, L, R。其中n为音符的个数，k为乐曲所包含的超级和弦个数，L和R分别是超级和弦所包含音符个数的下限和上限。
接下来n行，每行包含一个整数Ai，表示按编号从小到大每个音符的美妙度。
输出描述
只有一个整数，表示乐曲美妙度的最大值。
示例1
输入:
4 3 2 3 3 2 -6 8
输出:
11
说明:
共有5种不同的超级和弦：C++11(clang++ 3.9) 解法, 执行用时: 480ms, 内存消耗: 90960K, 提交时间: 2020-03-08 21:47:00
#include <bits/stdc++.h>
#define A 500010
#define B 2010
using namespace std;
typedef long long ll;
int n, k, l, r; ll a[A], f[A][20], ans;
struct node {
int s, l, r, t;
friend bool operator < (const node x, const node b) {
return a[x.t] - a[x.s - 1] < a[b.t] - a[b.s - 1];
}
};
int maxx(int x, int y) {return a[x] > a[y] ? x : y;}
int ask(int x, int y) {
int k = log2(y - x + 1);
return maxx(f[x][k], f[y - (1 << k) + 1][k]);
}
priority_queue<node> q;
int main(int argc, char const *argv[]) {
cin >> n >> k >> l >> r;
for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), f[i][0] = i, a[i] += a[i - 1];
for (int j = 1; 1 << j <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++)
f[i][j] = maxx(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
for (int i = 1; i + l - 1 <= n; i++) q.push(node{i, i + l - 1, min(i + r - 1, n), ask(i + l - 1, min(n, i + r - 1))});
while (k--) {
node fr = q.top(); q.pop(); ans += a[fr.t] - a[fr.s - 1];
if (fr.l != fr.t) q.push(node{fr.s, fr.l, fr.t - 1, ask(fr.l, fr.t - 1)});
if (fr.r != fr.t) q.push(node{fr.s, fr.t + 1, fr.r, ask(fr.t + 1, fr.r)});
}
cout << ans << endl;
return 0;
}