这也算是第K大问题的套路题了（虽然我一开始还想了个假算法），大体想法就是先弄出最优的一批解，然后每次从中提出一个最优解并转移到一个次优解，用优先队列维护这个过程即可。
类似的问题很多，放在序列上的，放在图上的，改天可以考虑补个专题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a[N],s[N],st[N][20],stp[N][20],n,k,L,R;
int query(int l,int r)
{
int lg=log2(r-l+1);
int tmp = max(st[l][lg],st[r-(1<<lg)+1][lg]);
if(tmp==st[l][lg]) return stp[l][lg];
else return stp[r-(1<<lg)+1][lg];
}
inline int eval(int o,int l,int r)
{
return s[query(l,r)]-s[o-1];
}
struct Item
{
int o,l,r;
bool operator < (const Item &b) const
{
return eval(o,l,r) < eval(b.o,b.l,b.r);
}
};
Item gen(int o,int l,int r)
{
Item tmp;
tmp.o=o;
tmp.l=l;
tmp.r=r;
return tmp;
}
priority_queue <Item> q;
int ans = 0;
signed main()
{
cin>>n>>k>>L>>R;
for(int i=1;i<=n;i++)
{
cin>>a[i];
s[i]=s[i-1]+a[i];
st[i][0]=s[i];
stp[i][0]=i;
}
for(int j=1;j<=19;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
{
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
if(st[i][j]==st[i][j-1])
stp[i][j]=stp[i][j-1];
else
stp[i][j]=stp[i+(1<<(j-1))][j-1];
}
for(int i=1;i+L-1<=n;i++)
{
q.push(gen(i,i+L-1,min(i+R-1,n)));
}
while(k--)
{
Item p=q.top();
q.pop();
int tans = eval(p.o,p.l,p.r);
ans += tans;
int mid = query(p.l,p.r);
if(mid!=p.l)
{
Item x=p;
x.r=mid-1;
if(x.r>=x.l) q.push(x);
}
if(mid!=p.r)
{
Item x=p;
x.l=mid+1;
if(x.r>=x.l) q.push(x);
}
}
cout<<ans<<endl;
}