求调 悬一关

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
int n,k,l,r,a[N],sum[N],ans;
struct node_{
	int i,lp,rp,o,val;
	friend bool operator<(node_ a,node_ b){
		return a.val<b.val;
	}
};
struct node{
	int l,r,mx,mxid;
}t[N*4];
void pushup(int rt){
	if(t[rt].mx<t[rt<<1].mx) t[rt].mx=t[rt<<1].mx,t[rt].mxid=t[rt<<1].mxid;
	if(t[rt].mx<t[rt<<1|1].mx) t[rt].mx=t[rt<<1|1].mx,t[rt].mxid=t[rt<<1|1].mxid;
	return;
}
void init(int l,int r,int rt=1){
	t[rt].l=l,t[rt].r=r;
	if(l==r){
		t[rt].mx=a[l],t[rt].mxid=l;
		return;
	}
	int mid=(l+r)>>1;
	init(l,mid,rt<<1);
	init(mid+1,r,rt<<1|1);
	pushup(rt);
	return;
}
int query(int l,int r,int rt=1){
	if(t[rt].l>=l&&t[rt].r<=r) return t[rt].mxid;
	int ans=-9e18,id=0,mid=(t[rt].l+t[rt].r)>>1;
	if(l<=mid){
		int x=query(l,r,rt<<1);
		if(ans<a[x]) ans=a[x],id=x;
	}
	if(r>mid){
		int x=query(l,r,rt<<1|1);
		if(ans<a[x]) ans=a[x],id=x;
	}
	return id;
}
priority_queue <node_> q;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>k>>l>>r;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
	}
	init(1,n);
	for(int i=1;i<=n-l+1;i++){
		int lp=i+l-1,rp=min(i+r-1,n),o=query(lp,rp),val=sum[o]-sum[i-1];
		q.push({i,lp,rp,o,val});
	}
	while(k--){
		node_ t=q.top();
		q.pop();
		ans+=t.val;
		int o1=query(t.lp,t.o-1),o2=query(t.o+1,t.rp);
		q.push({t.i,t.lp,t.o-1,o1,sum[o1]-sum[t.i-1]});
		q.push({t.i,t.o+1,t.rp,o2,sum[o2]-sum[t.i-1]});
	}
	cout<<ans;
	return 0;
}