BZOJ-3065: 带插入区间K小值

Description

带插入、修改的区间k小值在线查询。原序列长度 <= 35000 插入个数 <= 35000，修改个数 <= 70000，查询个数 <= 70000 ,0 <= 每时每刻的权值 <= 70000

替罪羊树套权值线段树
作死写指针，写了一天。。。
替罪羊维护区间，每个节点维护子树所有节点权值的权值线段树。
并没有用函数式线段树，对于每个节点都是一个独立的线段树【一开始写函数式线段树不是RE就是MLE，之后就弃疗了】。
时间复杂度O(nlog^3n)

NOTE:
1.权值线段树插入的时候是新建节点的
2.寻找覆盖区间的线段树和单点的时候有可能出现l>r的情况
3.查询的时候需要调用到空接点的儿子，需要将null的儿子设为null
4.gdb是个好东西啊！
5.没事别作死写指针啊！

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? EOF : *p1++;
}
void read(int &x)
{
    x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
}
void read(char &ch) {ch=nc(); while(ch<'A'||ch>'Z') ch=nc();}

struct seg
{
    seg *ls,*rs;
    int siz;
    seg();
}*null=new seg();
seg::seg()
{
    ls=rs=null ? null : this;
    siz=0;
}
seg *seg_merge(seg *x,seg *y,int l,int r)
{
    if(x==null&&y==null) return null;
    seg *re=new seg();
    if(l==r)
    {
        re->siz=x->siz+y->siz;
        return re;
    }
    int mid=(l+r)>>1;
    re->ls=seg_merge(x->ls,y->ls,l,mid);
    re->rs=seg_merge(x->rs,y->rs,mid+1,r);
    re->siz=x->siz+y->siz;
    return re;
}
void seg_insert(seg *&p,seg *z,int l,int r,int x,int y)
{
    p=new seg(); p->siz=z->siz+y;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(x<=mid) p->rs=z->rs,seg_insert(p->ls,z->ls,l,mid,x,y);
    else p->ls=z->ls,seg_insert(p->rs,z->rs,mid+1,r,x,y);
    if(z!=null) free(z);
    if(!p->siz) free(p),p=null;
}
void Free(seg *x)
{
    if(x==null) return ;
    Free(x->ls);
    Free(x->rs);
    free(x);
}

int n,m,ans,w[141000];
double arf=0.8;
struct sheep
{
    sheep *ls,*rs;
    seg *tr;
    int k,siz,ms;
    sheep();
}*Null=new sheep(),*rot=Null;
int cgg;
sheep::sheep()
{
    tr=null; k=0;
    ls=rs=Null ? Null : this;
    ms=siz=(Null?1:0);
}
sheep *build(int l,int r)
{
    if(l>r) return Null;
    int mid=(l+r)>>1;
    sheep *re=new sheep();
    re->k=w[mid]; re->ls=build(l,mid-1); re->rs=build(mid+1,r);
    re->tr=seg_merge(re->ls->tr,re->rs->tr,0,70000);
    if(re->tr==null) re->tr=new seg();
    seg_insert(re->tr,re->tr,0,70000,re->k,1);
    re->ms=re->siz=re->ls->siz+re->rs->siz+1;
    return re;
}
void flatten(sheep *x)
{
    if(x==Null) return ;
    flatten(x->ls);
    w[++cgg]=x->k; Free(x->tr);
    flatten(x->rs); free(x);
}
void rebuild(sheep *&x)
{
    cgg=0; flatten(x);
    x=build(1,cgg);
}
void insert(sheep *&p,int x,int y,int fl)
{
    if(p==Null)
    {
        p=new sheep(); p->k=y;
        seg_insert(p->tr,p->tr,0,70000,y,1);
        return ;
    }
    p->siz++; seg_insert(p->tr,p->tr,0,70000,y,1); p->ms=max(p->siz,p->ms);
    if(x<=p->ls->siz)
    {
        if(!fl && p->ls->siz+1 > p->ms*arf) insert(p->ls,x,y,fl=1),rebuild(p);
        else insert(p->ls,x,y,0);
    }
    else
    {
        x-=(p->ls->siz+1);
        if(!fl && p->rs->siz+1 > p->ms*arf) insert(p->rs,x,y,fl=1),rebuild(p);
        else insert(p->rs,x,y,0);
    }
}
int Fix(sheep *p,int x,int y)
{
    int re;
    if(x<=p->ls->siz) re=Fix(p->ls,x,y);
    else
    {
        x-=(p->ls->siz+1);
        if(!x)
        {
            int re=p->k;
            seg_insert(p->tr,p->tr,0,70000,p->k,-1);
            p->k=y; seg_insert(p->tr,p->tr,0,70000,p->k,1);
            return re;
        }
        re=Fix(p->rs,x,y);
    }
    seg_insert(p->tr,p->tr,0,70000,re,-1);
    seg_insert(p->tr,p->tr,0,70000,y,1);
    return re;
}
seg *rt[500];
int val[500],cnt1,cnt2;
void init(sheep *p,int l,int r)
{
    if(l>r) return ;
    if(l==1&&r==p->siz)
    {
        if(p->siz==1) val[++cnt2]=p->k;
        else rt[++cnt1]=p->tr;
        return ;
    }
    if(r<=p->ls->siz+1)
    {
        if(r==p->ls->siz+1) val[++cnt2]=p->k,--r;
        init(p->ls,l,r);
    }
    else if(l>p->ls->siz)
    {
        l-=p->ls->siz;
        (l==1) ? val[++cnt2]=p->k : l--;
        init(p->rs,l,r-p->ls->siz-1);
    }
    else
    {
        val[++cnt2]=p->k;
        init(p->ls,l,p->ls->siz);
        init(p->rs,1,r-p->ls->siz-1);
    }
}
void Query()
{
    int l,r,k; read(l); read(r); read(k);
    l^=ans; r^=ans; k^=ans;
    cnt1=cnt2=0; init(rot,l,r);
    l=0; r=70000; int mid,tmp;
    while(l!=r)
    {
        mid=(l+r)>>1; tmp=0;
        for(int i=1;i<=cnt2;++i) tmp+=(val[i]>=l&&val[i]<=mid);
        for(int i=1;i<=cnt1;++i) tmp+=rt[i]->ls->siz;
        if(k<=tmp)
        {
            r=mid;
            for(int i=1;i<=cnt1;++i) rt[i]=rt[i]->ls;
        }
        else
        {
            k-=tmp; l=mid+1;
            for(int i=1;i<=cnt1;++i) rt[i]=rt[i]->rs;
        }
    }
    printf("%d\n",ans=l);
}
void Change()
{
    int x,y; read(x); read(y); x^=ans; y^=ans;
    Fix(rot,x,y);
}
void Insert()
{
    int x,y; read(x); read(y); x^=ans; y^=ans;
    insert(rot,x-1,y,0);
}

int main()
{
    read(n); for(int i=1;i<=n;++i) read(w[i]);
    rot=build(1,n); read(m); char sw;
    while(m--)
    {
        read(sw);
        switch(sw)
        {
            case 'Q': Query(); break;
            case 'M': Change(); break;
            case 'I': Insert(); break;
        }
    }
    return 0;
}