挺神奇的一道题，唯一想不通的是为什么放在主席树的题单里..
首先暴力找出所有的合法区间显然是不可能的。
考虑怎么贪心，假如固定每个L作为左端点，那么合法的区间就是[L+l-1,L+r-1]（当然还要跟n取个min）
对于每个L，用线段树求出合法区间内最大的值，以及取得最大值时所对应的点，设为idx
然后我们维护一个堆，把这些区间都丢进去，算答案时取最大的。
然后呢？第二大呢？
显然对于第一轮没有被选到的区间，不需要考虑它们是否会产生新的最大
那么答案就呼之欲出啦，可能产生第二大的就是被选中的区间内其他的点
我们把被选中的区间[L+l-1,L+r-1]分裂成 [L+l-1,idx-1] 和 [idx+1,L+r-1]；
然后再丢进去，做K次:D
#include<bits/stdc++.h> #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ls (rt<<1) #define rs (rt<<1|1) using namespace std; const int maxn=5e5+5; int n,k,l,r,a[maxn],sum[maxn]; struct tree{ int mx,idx; }t[maxn<<2]; void push_up(int rt){ if(t[ls].mx>=t[rs].mx){ t[rt]=t[ls]; } else t[rt]=t[rs]; } void build(int rt,int l=1,int r=n){ if(l==r){ t[rt].mx=sum[l]; t[rt].idx=l; return; } int mid=l+r>>1; build(ls,l,mid);build(rs,mid+1,r); push_up(rt); } int query(int ql,int qr,int rt=1,int l=1,int r=n){ if(ql<=l&&r<=qr){ return t[rt].idx; } int mid=l+r>>1; int ans1=0,ans2=0; if(ql<=mid) ans1=query(ql,qr,ls,l,mid); if(qr>mid) ans2=query(ql,qr,rs,mid+1,r); if(!ans1) return ans2; else if(!ans2) return ans1; else if(sum[ans1]>=sum[ans2]) return ans1; else return ans2; } struct point{ int l,r,val,id,L; bool operator > (const point a) const{ return val<a.val; } }; priority_queue<point,vector<point>,greater<point>>q; int main(){ //freopen("lys.in","r",stdin); fastio; cin>>n>>k>>l>>r; for(int i=1;i<=n;i++) { cin>>a[i],sum[i]=sum[i-1]+a[i]; } build(1); for(int i=1;i<=n;i++){ int lef=i+l-1,rig=i+r-1; rig=min(rig,n);lef=min(lef,n); if(lef-i+1<l) continue; int idx=query(lef,rig); //cout<<"id: "<<i<<" "<<lef<<" "<<rig<<" "<<idx<<endl; q.push((point){lef,rig,sum[idx]-sum[i-1],idx,i}); } //cout<<"finished"<<endl; long long tot=0; int cnt=k; while(cnt--){ point Top=q.top(); q.pop(); tot=tot+Top.val; int idx=Top.id,lef=Top.l,rig=Top.r,L=Top.L; //cout<<"add: "<<idx<<" "<<lef<<" "<<rig<<" "<<Top.val<<" "<<L<<endl; if(idx>lef){ if(lef-L+1>=l){ int id=query(lef,idx-1); q.push((point){lef,idx-1,sum[id]-sum[L-1],id,L}); } } if(idx<rig){ if(idx+1-L+1>=l){ int id=query(idx+1,rig); q.push((point){idx+1,rig,sum[id]-sum[L-1],id,L}); } } } cout<<tot<<endl; }