题目链接
题意
给定一个长度为 (n) 的数列 (a) ，对于其长度在 (l) 到 (r) 之间的若干个子区间的 区间和，求最大的 (k) 个值的和。
思路
参考自 FZHvampire
首先，预处理出前缀和。
如果要求最大值，很显然的想法是：枚举右端点 (i)，对于可行的区间 ([i-r+1, i-l+1]) 求得一个最大值 ，然后(n)个最大值中取一个最大的，复杂度 (NlogN)。
现在要求最大的k个值，怎么办呢？
回想一下，有这么一道趣味题。
将20匹马分成5组（组内有序），每次只能让4匹马赛跑，现要找出跑的最快的4匹马，最少要多少次呢？
做法是，先让各组跑的最快的4匹马比赛，找出最快的踢掉它，然后让该组的第二和其他组的第一跑，再决出第一并踢掉，让该组的下一个上位，依次类推。4次即能找出跑的最快的4匹马。
再想想这道题，好像有那么点联系。
每次找最优的，可以用 堆。
最优 则是指区间和最大。
每次踢掉最优的让下一个上位 又怎么体现呢？
维护一个元素为五元组 ({i, l, r, p, val})的堆，意为：
左端点在 ([l, r]) 区间内，右端点为 (i) 的这些区间中，最大的区间和 在 左端点为 (p) 时 取到，区间和为 (val).
那么 踢掉最优的 即为 取 pq.top()，
让下面的上位 即为 将这段区间拆成 除中间最优点外 的 两部分 重新插入到堆中，即插入 [l, p-1] 段与 [p+1, r] 段。
看题解时觉得是很巧妙的做法了，按照上面的思路仔细梳理一下，其实自己也是可以想出来的。
Code
#include <bits/stdc++.h>
#define maxn 500010
using namespace std;
typedef long long LL;
int a[maxn], n;
LL pre[maxn];
struct node { LL x; int p; }mn[maxn][32];
struct qnode {
int i, l, r, p; LL val;
bool operator < (const qnode& nd) const {
return val < nd.val;
}
};
priority_queue<qnode> pq;
void rmqInit() {
for (int i = 1; i <= n; ++i) mn[i][0] = {pre[i], i};
for (int j = 1; (1 << j) <= n; ++j) {
for (int i = 1; i + (1 << (j-1)) - 1 <= n; ++i) {
mn[i][j] = mn[i][j-1].x < mn[i + (1<<(j-1))][j-1].x ? mn[i][j-1] : mn[i + (1<<(j-1))][j-1];
}
}
}
int query(int l, int r) {
int k = (int)(log((double)r-l+1)/log((double)2));
return mn[l][k].x < mn[r-(1<<k)+1][k].x ? mn[l][k].p : mn[r-(1<<k)+1][k].p;
}
int main() {
int k, l, r;
scanf("%d%d%d%d", &n, &k, &l, &r);
pre[1] = 0;
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), pre[i+1] = pre[i] + a[i];
rmqInit();
for (int i = l; i <= n; ++i) {
int ll = max(1, i - r + 1), rr = i - l + 1,
p = query(ll, rr);
pq.push({i, ll, rr, p, pre[i+1] - pre[p]});
}
LL ans = 0;
while (k--) {
qnode qnd = pq.top(); pq.pop();
ans += qnd.val;
int l1 = qnd.l, r1 = qnd.p - 1,
l2 = qnd.p + 1, r2 = qnd.r,
i = qnd.i;
if (l1 <= r1) {
int p1 = query(l1, r1);
pq.push({i, l1, r1, p1, pre[i+1] - pre[p1]});
}
if (l2 <= r2) {
int p2 = query(l2, r2);
pq.push({i, l2, r2, p2, pre[i+1] - pre[p2]});
}
}
printf("%lld
", ans);
return 0;
}