用的主席树,主席树部分应该没问题(
#include<bits/stdc++.h>
#define ili inline
#define pb push_back
using namespace std;
template <typename T>
ili void rd(T&x){
int f=1;x=0;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0' && c<='9'){
x=(x<<3)+(x<<1)+(c^48);
c=getchar();
}
x=f*x;
}
template <typename T,typename ...Args>
ili void rd(T &x,Args&...args){
rd(x),rd(args...);
}
template <typename T>
void wr(T x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x+'0');
else wr<T>(x/10),putchar(x%10+'0');
}
const int N=5e5+5;
const int LG=20;
int n,k,L,R;
int a[N],sum[N],b[N],idx;
struct node{
int ans,r,tim;
};
bool operator <(node a,node b){
return a.ans<b.ans;
}
priority_queue<node> q;
int P=1,DEP,t[N*3+N*LG],son[N*3+N*LG][2],OST,rt[N];
int ans;
ili void update(int i,int ver,int l,int k){
int tl=l+P;
int v=rt[ver];
rt[i]=l=++OST;
t[l]=t[v]+k;
for(int dep=DEP-1;dep>=0;dep--){
if((tl>>dep)&1) son[l][0]=son[v][0],son[l][1]=++OST,v=son[v][1];
else son[l][1]=son[v][1],son[l][0]=++OST,v=son[v][0];
l=OST,t[l]=t[v]+k;
}
}
ili int query(int l,int r,int k){
l=rt[l],r=rt[r];
int tl=1;
for(int dep=DEP;dep;dep--){
int num=t[son[r][0]]-t[son[l][0]];
if(num>=k){
l=son[l][0];
r=son[r][0];
tl=tl<<1;
}else{
k-=num;
l=son[l][1];
r=son[r][1];
tl=tl<<1|1;
}
}
return tl-P;
}
ili void zkw(){
rt[0]=1;
while(P<=idx+1) P<<=1,++DEP;
OST=(P<<1)-1;
for(int i=P-1;i;i--) son[i][0]=i<<1,son[i][1]=i<<1|1;
for(int i=1;i<=n;i++){
update(i,i-1,a[i],1);
}
}
ili void xpigeon(){
rd(n,k,L,R);
for(int i=1;i<=n;i++){
rd(a[i]);
sum[i]=a[i]+sum[i-1];
b[i]=sum[i];
}
sort(b+1,b+n+1);
idx=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++){
a[i]=lower_bound(b+1,b+idx+1,sum[i])-b;
}
zkw();
for(int r=L;r<=n;r++){
int u=max(r-R,1);
int v=r-L;
if(r-R<=0&&b[query(0,v,1)]>0) q.push((node){sum[r],r,1});
else{
q.push((node){sum[r]-b[query(u-1,v,1)],r,1});
}
}
for(int i=1;i<=k;i++){
node tmp=q.top();
q.pop();
ans+=tmp.ans;
//cout<<tmp.ans<<" "<<tmp.r<<" "<<tmp.tim<<'\n';
int u=max(tmp.r-R,1);
int v=tmp.r-L;
if(u+tmp.tim>v) continue;
if(tmp.r-R<=0 && b[query(0,v,tmp.tim+1)]>0) q.push((node){sum[tmp.r],tmp.r,tmp.tim+1});
else{
q.push((node){sum[tmp.r]-b[query(u+tmp.tim-1,v,1)],tmp.r,tmp.tim+1 });
}
}
cout<<ans<<'\n';
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
xpigeon();
return 0;
}