WC时候写的题，补一下

做法比较巧妙：记录每个位置和它当前对应区间的左右端点，做前缀和之后重载一下小于号，用优先队列+ST表维护当前最大值。这样贡献就是区间最大值和端点左边差分一下，可以O(1)得到。每次从最大值所在位置分裂成两个小的对应区间扔回优先队列里即可。

1 // luogu-judger-enable-o2 2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 const int N=500005,M=21; 9 int n,k,l,r;10 long long ans;11 int val[N],sum[N];12 pair
           
             st[N][M];13 void Make_ST()14 {15 int lgg=log2(n);16 for(int i=1;i<=n;i++) st[i][0]=make_pair(sum[i],i);17 for(int i=1;i<=lgg;i++)18 for(int j=1;j<=n-(1<
            
              Qmax(int l,int r)22 {23 int lgg=log2(r-l+1);24 return max(st[l][lgg],st[r-(1<
             
               tmp=Qmax(lpt,rpt);32 return tmp.first-sum[pts-1];33 }34 };35 bool operator < (a x,a y)36 {37 return x.Maxi()
              
                hp;40 void Insert(int nd,int ll,int rr)41 {42 if(ll>rr) return;43 hp.push((a){nd,ll,rr});44 }45 int main()46 {47 scanf("%d%d%d%d",&n,&k,&l,&r);48 for(int i=1;i<=n;i++)49 scanf("%d",&val[i]),sum[i]=sum[i-1]+val[i];50 Make_ST();51 for(int i=1;i<=n;i++)52 if(i+l-1<=n) hp.push((a){i,i+l-1,min(n,i+r-1)});53 for(int i=1;i<=k;i++)54 {55 a tmp=hp.top(); 56 hp.pop(),ans+=tmp.Maxi();57 int nd=tmp.pts,ll=tmp.lpt,rr=tmp.rpt;58 int pt=Qmax(ll,rr).second;59 Insert(nd,ll,pt-1),Insert(nd,pt+1,rr); 60 }61 printf("%lld",ans);62 return 0;63 }