其实用主席树理论上来说复杂度会小一点，因为 ST 表做法会把一个候选项拆成两个。
显然的套路，用堆来维护每个左端点对应的和最大的右端点，然后取 \(k\) 次。
每次把原来的候选区间 \([l,r]\) 分成 \([l,x),(x,r]\)，其中 \(x\) 是最大值。
代码： 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
using namespace std;
const int N = 5e5;
const int LG = 20;
int n,k,L,R;
int a[N + 5],sum[N + 5],lg2[N + 5];
int st[N + 5][LG + 5];
long long ans;
inline int query(int l,int r)
{
int lg = lg2[r - l + 1];
return sum[st[l][lg]] > sum[st[r - (1 << lg) + 1][lg]] ? st[l][lg] : st[r - (1 << lg) + 1][lg];
}
struct note
{
int v,x,l,r;
inline bool operator<(const note &o) const
{
return sum[v] - sum[x - 1] < sum[o.v] - sum[o.x - 1];
}
};
__gnu_pbds::priority_queue<note> q;
int main()
{
scanf("%d%d%d%d",&n,&k,&L,&R);
for(register int i = 2;i <= n;++i)
lg2[i] = lg2[i / 2] + 1;
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),sum[i] = sum[i - 1] + a[i],st[i][0] = i;
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
st[j][i] = sum[st[j][i - 1]] > sum[st[j + (1 << i - 1)][i - 1]] ? st[j][i - 1] : st[j + (1 << i - 1)][i - 1];
for(register int i = 1;i + L - 1 <= n;++i)
q.push((note){query(i + L - 1,min(i + R - 1,n)),i,i + L - 1,min(i + R - 1,n)});
while(k--)
{
note p = q.top();
q.pop();
ans += sum[p.v] - sum[p.x - 1];
if(p.l < p.v)
q.push((note){query(p.l,p.v - 1),p.x,p.l,p.v - 1});
if(p.r > p.v)
q.push((note){query(p.v + 1,p.r),p.x,p.v + 1,p.r});
}
printf("%lld\n",ans);
}