bzoj3110: [Zjoi2013]K大数查询 树套数

#include <algorithm>
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int getint()
{
    int res;char c;
    while(c=getchar(),c<'0'||c>'9');
    res=c-'0';
    while(c=getchar(),c>='0'&&c<='9')
    res=res*10+c-'0';
    return res;
}
int n,m,siz;
int root[200005];
int ls[20000005],rs[20000005],sum[20000005],add[20000005];
void pushdown(int rt,int l,int r)
{
    if(!add[rt]||l==r) return;
    if(!ls[rt]) siz++,ls[rt]=siz;
    if(!rs[rt]) siz++,rs[rt]=siz;
    add[ls[rt]]+=add[rt];
    add[rs[rt]]+=add[rt];
    int mid=(l+r)>>1;
    sum[ls[rt]]+=(mid-l+1)*add[rt];
    sum[rs[rt]]+=(r-mid)*add[rt];
    add[rt]=0;
}
void pushup(int rt)
{
    sum[rt]=sum[ls[rt]]+sum[rs[rt]];
}
void update(int &rt,int r,int x,int y)
{
    if(!rt) siz++,rt=siz;
    //pushdown(rt,l,r);
    if(x<=l&&r<=y)
    {
        add[rt]++;
        sum[rt]+=(r-l+1);
        return;
    }
    pushdown(rt,r);
    int mid=(l+r)>>1;
    if(x<=mid) update(ls[rt],mid,x,y);
    if(y>mid) update(rs[rt],mid+1,r,y);
    pushup(rt);
}
int query(int rt,int y)
{
    if(!rt) return 0;
    //pushdown(rt,r);
    if(x<=l&&r<=y)
    {
        return sum[rt];
    }
    pushdown(rt,r);
    int mid=(l+r)>>1;
    int ans=0;
    if(x<=mid) ans+=query(ls[rt],y);
    if(y>mid) ans+=query(rs[rt],y);
    return ans;
}
void qadd(int x,int y,int v)
{
    int rt=1,l=1,r=n;
    while(l<r)
    {
        mid=(l+r)>>1;
        update(root[rt],1,n,y);
        if(v<=mid)
        {
            r=mid;
            rt=rt<<1;
        }
        else
        {
            l=mid+1;
            rt=rt<<1|1;
        }
    }
    update(root[rt],y);
}
inline int getans(int x,int c)
{
    int l=1,r=n,k=1;
    while(l<r)
    {
        int mid=(l+r)>>1;
        int t=query(root[k<<1],y);
        if(t>=c)r=mid,k<<=1;
        else l=mid+1,k=k<<1|1,c-=t;
    }
    return l;
}
int main()
{
    int opt,k;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d%d",&opt,&l,&r,&k);
        if(opt==1)
        {
            qadd(l,n-k+1);
        }
        else printf("%dn",n-getans(l,k)+1);
    }
    return 0;
}