由于k较小，因此考虑不断选取最大值，但同时还要删掉最大值。记f(k,l,r)表示以k为右端点时左端点在l~r之间的最大值，这个可以用线段树快速求出。当发现最大值是f(k,l,r)时，假设在位置t取到，则删除f(k,l,r)并加入f(k,l,t-1)和f(k,t+1,r)，这个可以用堆来维护。初始时加入f(k,k-r,k-l)即可，注意判0。
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 #define L (k<<1) 5 #define R (L+1) 6 #define mid (l+r>>1) 7 int n,m,l,r,k,s[N],f[N<<2]; 8 struct ji{ 9 int k,x,y,z; 10 bool operator < (const ji &a)const{ 11 return s[k]-s[z]<s[a.k]-s[a.z]; 12 } 13 }; 14 priority_queue<ji>q; 15 int up(int x,int y){ 16 if (s[x]<s[y])return x; 17 return y; 18 } 19 void update(int k,int l,int r,int x){ 20 if (l==r){ 21 f[k]=l; 22 return; 23 } 24 if (x<=mid)update(L,l,mid,x); 25 else update(R,mid+1,r,x); 26 f[k]=up(f[L],f[R]); 27 } 28 int query(int k,int l,int r,int x,int y){ 29 if ((l>y)||(x>r))return n+1; 30 if ((x<=l)&&(r<=y))return f[k]; 31 return up(query(L,l,mid,x,y),query(R,mid+1,r,x,y)); 32 } 33 void add(int k,int x,int y){ 34 q.push(ji{k,x,y,query(1,0,n,x,y)}); 35 } 36 int main(){ 37 scanf("%d%d%d%d",&n,&m,&l,&r); 38 update(1,0,n,0); 39 for(int i=1;i<=n;i++){ 40 scanf("%d",&k); 41 s[i]=s[i-1]+k; 42 update(1,0,n,i); 43 } 44 s[n+1]=0x3f3f3f3f; 45 for(int i=l;i<=n;i++)add(i,max(i-r,0),i-l); 46 long long ans=0; 47 for(int i=1;i<=m;i++){ 48 ji o=q.top(); 49 ans+=s[o.k]-s[o.z]; 50 q.pop(); 51 if (o.x<o.z)add(o.k,o.x,o.z-1); 52 if (o.z<o.y)add(o.k,o.z+1,o.y); 53 } 54 printf("%lld",ans); 55 }