思路

和十二省联考D1T2相似的思路

用堆维护最大值，取出一个位置之后把这个位置的下一个值插入堆

注意插入的数有负数，并且开long long

代码

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define int long longusing namespace std;struct QNode{    int pos,kth,val;    bool operator < (const QNode &b) const{        return val
        
         >1;    if(pos<=mid)        insert(Seg[o].lson,l,mid,pos);    else        insert(Seg[o].rson,mid+1,r,pos);}int query(int Lroot,int Rroot,int l,int r,int kth){    if(l==r){        if(kth<=Seg[Rroot].sz-Seg[Lroot].sz)            return l;        else            return -0x3f3f3f3f;            }    int siz=Seg[Seg[Rroot].rson].sz-Seg[Seg[Lroot].rson].sz,mid=(l+r)>>1;    if(kth>siz)        return query(Seg[Lroot].lson,Seg[Rroot].lson,l,mid,kth-siz);    else        return query(Seg[Lroot].rson,Seg[Rroot].rson,mid+1,r,kth);}priority_queue
         
           q;signed main(){ scanf("%lld %lld %lld %lld",&n,&k,&Lx,&Rx); for(int i=1;i<=n;i++){ scanf("%lld",&sum[i]); sum[i]+=sum[i-1]; root[i]=root[i-1]; insert(root[i],1,1000000100,sum[i]+500000000); } for(int i=1;i<=n-Lx+1;i++){ int t=query(root[i+Lx-2],root[min(i+Rx-1,n)],1,1000000100,1)-500000000-sum[i-1]; // printf("t=%lld\n",t); q.push((QNode){i,1,t}); } int cnt=0; while(cnt