https://www.luogu.com.cn/record/100922294

#include<bits/stdc++.h>
#define N 100600
#define pii pair<int,int>
#define gc getchar()
using std::pair;
int n,m,d,t,a[N],sum[N],l,r,k,root;
void rd(int&x){
	int f=1;
	char c=gc;
	while(!isdigit(c)){
		if(c=='-')f=-1;
		c=gc;
	}
	while(isdigit(c))x=(x>>1)+(x>>3)+c-'0',c=gc;
	x*=f;
	return;
}
struct node{
	int now,t,l,r;
	int sum;
	bool operator<(const node&x)const{
		return sum<x.sum;
	}
};
std::priority_queue<node>q;
struct Segtree{
	#define f first
	#define s second
	#define mid ((a[p].l+a[p].r)>>1)
	int cnt;
	struct{
		int l,r,ls,rs;
		pii val;
	}a[N];
	pii max(pii a,pii b){
		if(a.f>b.f)return a;
		else return b;
	}
	void pushup(int p){
		a[p].val=max(a[a[p].ls].val,a[a[p].rs].val);
	}
	void build(int&p,int l,int r){
		if(!p){
			p=++cnt;
		}
		if(l==r){
			a[p].val=std::make_pair(sum[l],l);
			a[p].l=l;
			a[p].r=r;
			return;
		}
		a[p].l=l;
		a[p].r=r;
		build(a[p].ls,l,mid);
		build(a[p].rs,mid+1,r);
		pushup(p);
		return;
	}
	pii query(int p,int L,int R){
		if(L<=a[p].l&&a[p].r<=R){
			return a[p].val;
		}
		pii ans;
		if(L<=mid)ans=max(ans,query(a[p].ls,L,R));
		if(R>mid)ans=max(ans,query(a[p].rs,L,R));
		return ans;
	}
}T;
int main(){
	rd(n);rd(k);rd(l);rd(r);
//	scanf("%d%d%d%d",&n,&k,&l,&r);
	for(int i=1;i<=n;i++){
		//scanf("%d",a+i);
		rd(a[i]);
		sum[i]=sum[i-1]+a[i];
	}
	T.build(root,1,n);
	for(int i=1;i<=n;i++){
		int j=std::min(n,i+l-1);
		if(j-i+1<l)break;
		int k=std::min(n,i+r-1);
		pii x=T.query(root,j,k);
		q.push({i,x.s,j,k,x.f-sum[i-1]});
	}
	int ans=0;
	for(int i=1;i<=k;i++){
		node x=q.top();q.pop();
		ans+=x.sum;
		node y,z;
//		printf("%d %d %d %d %d\n",&x.now,&x.t,&x.l,&x.r,&x.sum);
		if(x.l!=x.t){
			pii y1=T.query(root,x.l,x.t-1);
			y={x.now,y1.s,x.l,x.t-1,y1.f-sum[i-1]};	
			q.push(y);
		}
		if(x.r!=x.t){
			pii z1=T.query(root,x.t+1,x.r);
			z={x.now,z1.s,x.t+1,x.r,z1.f-sum[i-1]};
			q.push(z);
		}
	}
	printf("%d\n",ans);
	return 0;
}