P2048 [NOI2010]超级钢琴

思路

和十二省联考D1T2相似的思路
用堆维护最大值，取出一个位置之后把这个位置的下一个值插入堆
注意插入的数有负数，并且开long long

代码

#include 
#include 
#include 
#include 
#define int long long
using 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