BZOJ 3065 替罪羊树+动态开节点线段树

//By SiriusRen

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=;

int root[],n,q,xx,yy,zz,Root,ans;

struct Segment_Tree{

    int rubbish[],top,tree[],lson[],rson[];

    int get_rubbish(){if(rubbish[top])return rubbish[top--];return top--;}

    void insert(int l,int r,int &pos,int num,int wei){

        if(!pos)pos=get_rubbish();

        if(l==r){tree[pos]+=wei;return;}

        int mid=(l+r)>>;

        if(mid>=num)insert(l,mid,lson[pos],num,wei);

        else insert(mid+,r,rson[pos],num,wei);

        tree[pos]=tree[lson[pos]]+tree[rson[pos]];

        if(!tree[lson[pos]]&&lson[pos])rubbish[++top]=lson[pos],lson[pos]=;

        if(!tree[rson[pos]]&&rson[pos])rubbish[++top]=rson[pos],rson[pos]=;

    }

    void merge(int x,int y,int &k){

        if(!k)k=get_rubbish();

        tree[k]=tree[x]+tree[y];

        if(lson[x]||lson[y])merge(lson[x],lson[y],lson[k]);

        if(rson[x]||rson[y])merge(rson[x],rson[y],rson[k]);

    }

    void dfs(int l,int r,int x){

        int mid=(l+r)>>;

        if(lson[x])dfs(l,mid,lson[x]),rubbish[++top]=lson[x];

        if(rson[x])dfs(mid+,r,rson[x]),rubbish[++top]=rson[x];

        lson[x]=rson[x]=tree[x]=;

    }

}segtree;

int top1,top2,stk1[],stk2[];

struct SC_TREE{

    int top,rubbish[],lson[],rson[],wei[],size[];

    int get_rubbish(){return rubbish[top--];}

    void build(int &k,int l,int r){

        if(l>r)return;

        if(!k)k=get_rubbish();

        int mid=(l+r)>>;wei[k]=stk2[mid];

        if(l==r){segtree.insert(,N,root[k],stk2[l],),size[k]=;return;}

        build(lson[k],l,mid-),build(rson[k],mid+,r);

        segtree.merge(root[lson[k]],root[rson[k]],root[k]);

        segtree.insert(,N,root[k],stk2[mid],);

        size[k]=size[lson[k]]+size[rson[k]]+;

    }

    void init(){for(int i=;i<=;i++)rubbish[i]=-i+;top=;segtree.top=,build(Root,,n);}

    int find_wei(int x,int sz){

        if(size[lson[x]]+==sz)return wei[x];

        else if(size[lson[x]]>=sz)return find_wei(lson[x],sz);

        else return find_wei(rson[x],sz-size[lson[x]]-);

    }

    void change(int x,int sz,int w,int last_w){

        segtree.insert(,N,root[x],last_w,-);

        segtree.insert(,N,root[x],w,);

        if(size[lson[x]]+==sz){wei[x]=w;return;}

        else if(size[lson[x]]>=sz)change(lson[x],sz,w,last_w);

        else change(rson[x],sz-size[lson[x]]-,w,last_w);

    }

    void query(int l,int r,int x){

        int L=size[lson[x]],R=size[x];

        if(l==&&R==r){stk1[++top1]=root[x];return;}

        if(l<=L+&&r>=L+)stk2[++top2]=wei[x];

        if(r<=L)query(l,r,lson[x]);

        else if(l>L+)query(l-L-,r-L-,rson[x]);

        else{

            if(l<=L)query(l,L,lson[x]);

            if(r>L+)query(,r-L-,rson[x]);

        }

    }

    int Query(int l,int r,int kth){

        top1=top2=;query(l,r,Root);

        int L=,R=N,ans=,M,temp;

        while(L<R){

            M=(L+R)>>;temp=;

            for(int i=;i<=top1;i++)temp+=segtree.tree[segtree.lson[stk1[i]]];

            for(int i=;i<=top2;i++)if(stk2[i]<=M&&stk2[i]>=L)temp++;

            if(temp>kth){for(int i=;i<=top1;i++)stk1[i]=segtree.lson[stk1[i]];R=M;}

            else {for(int i=;i<=top1;i++)stk1[i]=segtree.rson[stk1[i]];L=M+;kth-=temp;}

        }return L;

    }

    void dfs(int x){

        segtree.dfs(,N,root[x]);root[x]=;

        if(lson[x])dfs(lson[x]),rubbish[++top]=lson[x];

        stk2[++top2]=wei[x];

        if(rson[x])dfs(rson[x]),rubbish[++top]=rson[x];

        lson[x]=rson[x]=wei[x]=size[x]=;

    }

    int rebuild(int sz,int &x){top2=,dfs(x),build(x,,sz);}

    bool insert(int &x,int sz,int w){

        if(!x){x=get_rubbish();segtree.insert(,N,root[x],w,);size[x]=;wei[x]=w;return ;}

        segtree.insert(,N,root[x],w,),size[x]++;

        if(size[lson[x]]>=sz){if(insert(lson[x],sz,w))rebuild(size[lson[x]],lson[x]);}

        else if(insert(rson[x],sz-size[lson[x]]-,w))rebuild(size[rson[x]],rson[x]);

        if(max(size[lson[x]],size[rson[x]])>0.666*size[x])return ;return ;

    }

}SC_Tree;

int read(){

    int x=;char p=getchar();

    while(p<''||p>'')p=getchar();

    while(p>=''&&p<='')x=x*+p-'',p=getchar();

    return x;

}

char readchar(){char p=getchar();while(p!='Q'&&p!='M'&&p!='I')p=getchar();return p;}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d",&stk2[i]);

    SC_Tree.init();

    scanf("%d",&q);

    while(q--){

        char op=readchar();xx=read()^ans,yy=read()^ans;

        if(op=='Q')zz=read()^ans,printf("%d\n",ans=SC_Tree.Query(xx,yy,zz-));

        else if(op=='M')SC_Tree.change(Root,xx,yy,SC_Tree.find_wei(Root,xx));

        else SC_Tree.insert(Root,xx-,yy);

    }

}