草复制错了:
```cpp
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define ZYC using
#define AK namespace
#define IOI std
ZYC AK IOI;
const int N = 5e5 + 10;
int n, k;
ll sum[N], f[N][25], ans, L, R;
struct node
{
ll x, y, l, r;
inline bool operator < (const node& a) const
{
return sum[x] - sum[y] < sum[a.x] - sum[a.y];
}
};
priority_queue<node> q;
ll query (int l, int r)
{
int t = log2(r - l + 1);
return sum[f[l][t]] < sum[f[r - (1 << t) + 1][t]]? f[l][t]: f[r - (1 << t) + 1][t];
}
ll max(ll a, ll b) {return a > b? a: b;}
int main()
{
// freopen(".in", "r", stdin);
scanf("%d%d%d%d", &n, &k, &L, &R);
for (int i = 1; i <= n; i++)
scanf ("%lld", &sum[i]), sum[i] += sum[i - 1],
f[i][0] = i;
for (int j = 1; j <= 20; j++)
for (int i = 1; i + (1 << j - 1) <= n; i++)
f[i][j] = sum[f[i][j-1]] < sum[f[i+(1<<j-1)][j-1]]? f[i][j-1]: f[i+(1<<j-1)][j-1];
for (int i = L; i <= n; ++i)
q.push((node){i, query(max(i - R, 0LL), i - L), max(i - R, 0LL), i - L});
for (; k--; )
{
node x = q.top();q.pop();
ans += sum[x.x] - sum[x.y];
// printf ("%lld\n", sum[x.x] - sum[x.y]);
if (x.l != x.y) q.push((node){x.x, query(x.l, x.y - 1), x.l, x.y - 1});
if (x.r != x.y) q.push((node){x.x, query(x.y + 1, x.r), x.y + 1, x.r});
}
printf ("%lld\n", ans);
return 0;
}
```
这份才是
by Jayun @ 2021-01-29 21:32:59
我上面这份代码是找左端点,如果找右端点会更好。
by Jayun @ 2021-01-29 21:46:07