$Solution$
现设一个前缀和 $sum$ 和 $rmq$
$sum_i$ 表示 $1\sim i$ 的前缀和。
$f_{i, j}$ 表示 $i$ 前面连续 $2^j$ 个数中最大的 $sum$ 。
$g_{l, r}$ 表示使 $[l,r]$ 中 $sum$ 取到最大值的位置。
对于每一个 $i$ ($1\leq i \leq n$) ,有一个优先队列。
队列中的值形如 $(l, r, val)$ ,表示左端点为 $i$ ,右端点在区间 $[l, r]$ 的中,$val$ 表示以上连续段的最大值。
把所有 $i$ 的优先队列的队头插入全局优先队列中。
每一次取全局队列中的对头,找到它的来源(即 $(l, r, val)$ )并删除。
再把 $(l, g_{l, r} - 1, val)$ 和 $(g_{l, r} + 1, r, val)$ 插回去。
总时间复杂度 $O(n\log n)$
$Code$
#include <bits/stdc++.h>
using namespace std;
const int N = 500010;
int n, k, L, R;
int a[N];
int f[N][30], g[N][30];
struct GROUP1 {
int l, r, val;
bool operator < (const GROUP1 &b) const {
return val < b.val;
}
};
struct GROUP2 {
int id, val;
bool operator < (const GROUP2 &b) const {
return val < b.val;
}
};
priority_queue<GROUP1> q[N];
priority_queue<GROUP2> heap;
GROUP2 rmq(int l, int r) {
int len = log2(r - l + 1);
int a = f[l + (1 << len) - 1][len], b = f[r][len];
if (a <= b) return {g[r][len], b};
return {g[l + (1 << len) - 1][len], a};
}
int main() {
scanf("%d%d%d%d", &n, &k, &L, &R);
for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]), a[i] += a[i - 1];
for (int i = 1; i <= n; i ++ ) {
f[i][0] = a[i], g[i][0] = i;
for (int j = 1; j < 20; j ++ ) {
if (i < (1 << j)) break;
f[i][j] = max(f[i][j - 1], f[i - (1 << j - 1)][j - 1]);
if (f[i][j] == f[i][j - 1]) g[i][j] = g[i][j - 1];
else g[i][j] = g[i - (1 << j - 1)][j - 1];
}
}
for (int i = 1; i <= n - L + 1; i ++ ) {
int LL = i + L - 1, RR = min(i + R - 1, n);
int v = rmq(LL, RR).val - a[i - 1];
q[i].push({LL, RR, v});
heap.push({i, v});
}
long long res = 0;
while (k -- ) {
auto t = heap.top();
heap.pop();
res += t.val;
auto p = q[t.id].top();
q[t.id].pop();
int d = rmq(p.l, p.r).id;
if (p.l <= d - 1) q[t.id].push({p.l, d - 1, rmq(p.l, d - 1).val - a[t.id - 1]});
if (d + 1 <= p.r) q[t.id].push({d + 1, p.r, rmq(d + 1, p.r).val - a[t.id - 1]});
if (q[t.id].size())heap.push({t.id, q[t.id].top().val});
}
printf("%lld", res);
return 0;
}