30ptsRE求条（开10倍空间不知道怎么就过了）

#include<bits/stdc++.h>
#define int long long 
#define Maxn 50005 
using namespace std;
struct node {
	int i,l,r,mx,maxn;
	bool operator<(const node&is)
	const {return maxn < is.maxn;}
};
priority_queue<node> Q;
int pre[Maxn],stlist[Maxn][30];
void prepare(int n,int* a) {
//	for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<"\n";
	for(int i=1;i<=n;i++)stlist[i][0] = i;
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			stlist[i][j] = a[stlist[i][j-1]] > a[stlist[i+(1<<(j-1))][j-1]]?stlist[i][j-1]:stlist[i+(1<<(j-1))][j-1];
}
int query(int l,int r,int* a) {
	int o = log2(r-l+1);
	return a[stlist[l][o]] > a[stlist[r-(1<<o)+1][o]]?stlist[l][o]:stlist[r-(1<<o)+1][o];
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,k,l,r;
	cin>>n>>k>>l>>r;
	for(int i=1;i<=n;i++) {
		int x; cin>>x;
		pre[i] = pre[i-1]+x;
//		cout<<pre[i]<<" ";
	} 
//	cout<<"\n";
	prepare(n,pre);
	for(int i=1;i<=n-l+1;i++)
		Q.push({i,i+l-1,min(i+r-1,n),query(i+l-1,min(i+r-1,n),pre),pre[query(i+l-1,min(i+r-1,n),pre)]-pre[i-1]});
	int ans = 0;
	while(k --) {
		auto x = Q.top(); Q.pop();
		ans += x.maxn;
//		cout<<x.i<<" "<<x.l<<" "<<x.r<<" "<<x.mx<<"\n";
		if(x.mx != x.l)Q.push({x.i,x.l,x.mx-1,query(x.l,x.mx-1,pre),pre[query(x.l,x.mx-1,pre)]-pre[x.i-1]});
		if(x.mx != x.r)Q.push({x.i,x.mx+1,x.r,query(x.mx+1,x.r,pre),pre[query(x.mx+1,x.r,pre)]-pre[x.i-1]});
	} cout<<ans;
	return 0;
}