BZOJ2006[NOI2010]超级钢琴——堆+主席树

#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
#define pr pair<int,int>
using namespace std;
ll ans;
int n,m;
int x,y;
int L,R;
int cnt;
int s[500010];
int t[500010];
int root[500010];
int ls[30000010];
int rs[30000010];
int sum[30000010];
priority_queue<pr>q;
void updata(int &rt,int pre,int l,int r,int k)
{
    rt=++cnt;
    sum[rt]=sum[pre]+1;
    ls[rt]=ls[pre];
    rs[rt]=rs[pre];
    if(l==r)
    {
        return ;
    }
    int mid=(l+r)>>1;
    if(k<=mid)
    {
        updata(ls[rt],ls[pre],l,mid,k);
    }
    else
    {
        updata(rs[rt],rs[pre],mid+1,r,k);
    }
}
int query(int x,int y,int l,int r,int k)
{
    if(l==r)
    {
        return l;
    }
    int res=sum[rs[y]]-sum[rs[x]];
    int mid=(l+r)>>1;
    if(res<k)
    {
        return query(ls[x],ls[y],l,mid,k-res);
    }
    else
    {
        return query(rs[x],rs[y],mid+1,r,k);
    }
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&L,&R);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        s[i]=s[i-1]+x;
        updata(root[i],root[i-1],0,1000000000,s[i]+500000000);
    }
    for(int i=1;i+L-1<=n;i++)
    {
        t[i]++;
        x=query(root[i+L-2],root[min(n,i+R-1)],0,1000000000,t[i]);
        q.push(make_pair(x-s[i-1],i));
    }
    while(m)
    {
        pr miku=q.top();
        q.pop();
        m--;
        x=miku.first;
        y=miku.second;
        ans+=1ll*(x-500000000);
        if(t[y]<min(n,y+R-1)-(y+L-1)+1)
        {
            t[y]++;
            x=query(root[y+L-2],root[min(n,y+R-1)],0,1000000000,t[y]);
            q.push(make_pair(x-s[y-1],y));
        }
    }
    printf("%lld",ans);
}