【ZJOI2013】bzoj3110 K大数查询【解法二】

Description

有N个位置，M个操作。操作有两种，每次操作如果是1 a b c的形式表示在第a个位置到第b个位置，每个位置加入一个数c 如果是2 a b
c形式，表示询问从第a个位置到第b个位置，第C大的数是多少。 Input

第一行N，M 接下来M行，每行形如1 a b c或2 a b c Output

输出每个询问的结果

树套树做法见【这里】。
整体二分，定义子问题 solve(L,R,l,r) 表示解决区间 [L,R] 的修改和询问，涉及的答案的范围在 [l,r] 。二分答案 mid ，按时间顺序扫描，用线段树维护区间个数和，修改按照与 mid 的大小分成两类，其中大于 mid 的修改加入线段树，询问按照线段树中的个数 x 和自己的 k 的大小关系分成两类，其中 k>x 的 k 要减去 x 。然后把分成的两类分治下去。

#include<cstdio>
#include<algorithm>
using namespace std;
int rd()
{
    int x=0,f=1;
    char c=getchar();
    while (c<'0'||c>'9')
    {
        if (c=='-') f=-1;
        c=getchar();
    }
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
unsigned int rdu()
{
    unsigned int x=0;
    char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
struct str
{
    int o,l,r,id,res;
    unsigned int x;
}a[50010],b[50010],c[50010];
int ord[50010],ans[50010],tem[50010],n,q;
unsigned int sum[500010],tag[500010];
void clear(int p,int L,int R)
{
    if (tag[p]==-1)
    {
        sum[p]=0;
        if (L<R) tag[p<<1]=tag[p<<1|1]=-1;
        tag[p]=0;
    }
}
void down(int p,int R)
{
    clear(p,L,R);
    int mid=L+R>>1;
    if (tag[p])
    {
        sum[p]+=tag[p]*(R-L+1);
        if (L<R)
        {
            clear(p<<1,mid);
            tag[p<<1]+=tag[p];
            clear(p<<1|1,mid+1,R);
            tag[p<<1|1]+=tag[p];
        }
        tag[p]=0;
    }
}
void up(int p,int R)
{
    if (L==R) return;
    int mid=L+R>>1;
    down(p<<1,mid);
    down(p<<1|1,R);
    sum[p]=sum[p<<1]+sum[p<<1|1];
}
void modi(int p,int R,int l,int r)
{
    down(p,R);
    if (l<=L&&R<=r)
    {
        tag[p]++;
        down(p,R);
        return;
    }
    int mid=L+R>>1;
    if (l<=mid) modi(p<<1,mid,r);
    if (r>mid) modi(p<<1|1,R,r);
    up(p,R);
}
unsigned int qry(int p,R);
    if (l<=L&&R<=r) return sum[p];
    unsigned int ret=0;
    int mid=L+R>>1;
    if (l<=mid) ret+=qry(p<<1,r);
    if (r>mid) ret+=qry(p<<1|1,r);
    return ret;
}
void solve(int L,int r)
{
    if (l==r)
    {
        for (int i=L;i<=R;i++)
            if (a[i].o==2)
                a[i].res=l;
        return;
    }
    int mid=l+r>>1,n1=0,n2=0;
    unsigned int x;
    for (int i=L;i<=R;i++)
        if (a[i].o==1)
        {
            if (a[i].x>mid)
            {
                modi(1,1,a[i].l,a[i].r);
                c[++n2]=a[i];
            }
            else b[++n1]=a[i];
        }
        else
        {
            x=qry(1,a[i].r);
            if (x>=a[i].x)
                c[++n2]=a[i];
            else
            {
                a[i].x-=x;
                b[++n1]=a[i];
            }
        }
    tag[1]=-1;
    for (int i=1;i<=n1;i++)
        a[L+i-1]=b[i];
    for (int i=1;i<=n2;i++)
        a[L+n1+i-1]=c[i];
    solve(L,L+n1-1,mid);
    solve(L+n1,r);
}
int main()
{
    int nn=0;
    n=rd();
    q=rd();
    for (int i=1;i<=q;i++)
    {
        a[i].o=rd();
        a[i].l=rd();
        a[i].r=rd();
        a[i].id=i;
        if (a[i].o==1) tem[i]=ord[++nn]=rd();
        else a[i].x=rdu();
    }
    sort(ord+1,ord+nn+1);
    nn=unique(ord+1,ord+nn+1)-ord-1;
    for (int i=1;i<=q;i++)
        if (a[i].o==1)
            a[i].x=lower_bound(ord+1,ord+nn+1,tem[i])-ord;
    solve(1,q,nn);
    for (int i=1;i<=q;i++)
        if (a[i].o==2)
            ans[a[i].id]=a[i].res;
    for (int i=1;i<=q;i++)
        if (ans[i])
            printf("%dn",ord[ans[i]]);
}