人生第一道树套树。。（虽然暑假就写了= =）

　　这题是树状数组里面套个可持久化线段树。。。一开始想反了然后发现完全不会写TAT

　　一般的树状数组操作的时候是直接修改数组里的值的，套上可持久化线段树后就变成在相应的那颗线段树里面修改了。

　　修改操作就一个一个改，但查询第k大的时候要先把对应的线段树都存起来，然后一起算。。。

　　具体见代码吧= =

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #define rep1()for(register int i=1;i<=len1;i++) 6 #define rep2()for(register int i=1;i<=len2;i++) 7 using namespace std; 8 const int maxn=20233; 9 int num[maxn*17*17],lc[maxn*17*17],rc[maxn*17*17],rt[maxn];10 int L[20],R[20];11 struct zs{12     int num,id;13 }a[maxn];14 struct ask{15     int l,r,x;16     bool id;17 }q[10023];18 int b[maxn],c[maxn];19 int i,j,cnt,n,m,tot,len1,len2;20  21 int ra;char rx;22 inline int read(){23     rx=getchar(),ra=0;24     while(rx<'0'||rx>'9')rx=getchar();25     while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra;26 }27  28 inline int sum1(){
    int sum=0;rep1()sum+=num[L[i]];return sum;}29 inline int sum2(){
    int sum=0;rep2()sum+=num[R[i]];return sum;}30  31 inline void run1(int x){
    for(len1=0;x;x-=x&(-x))L[++len1]=rt[x];}32 inline void run2(int x){
    for(len2=0;x;x-=x&(-x))R[++len2]=rt[x];}33  34 void ins(int pre,int &now,int l,int r,int v){35     now=++tot;num[now]=num[pre]+1;36     if(l==r)return;int mid=(l+r)>>1;37     if(v<=mid)rc[now]=rc[pre],ins(lc[pre],lc[now],l,mid,v);38     else lc[now]=lc[pre],ins(rc[pre],rc[now],mid+1,r,v);39 }40 int query(int l,int r,int k){41     if(l==r)return l;42     int mid=(l+r)>>1,lsize=0;43     rep1()lsize-=num[lc[L[i]]];rep2()lsize+=num[lc[R[i]]];44     if(lsize>=k){45         rep1()L[i]=lc[L[i]];rep2()R[i]=lc[R[i]];46         return query(l,mid,k);47     }else{48         rep1()L[i]=rc[L[i]];rep2()R[i]=rc[R[i]];49         return query(mid+1,r,k-lsize);50     }51 }52 void change(int pre,int &now,int l,int r,int v,bool del){53     now=++tot,num[now]=num[pre]-(del?1:-1);54     if(l==r)return;int mid=(l+r)>>1;55     if(v<=mid)rc[now]=rc[pre],change(lc[pre],lc[now],l,mid,v,del);56     else lc[now]=lc[pre],change(rc[pre],rc[now],mid+1,r,v,del);57 }58 void build(int l,int r,int &x){59     x=++tot;60     if(l==r)build(l,(l+r)>>1,lc[x]),build(((l+r)>>1)+1,r,rc[x]);61 }62 bool cmp(zs a,zs b){
    return a.num
          
           n)q[a[i].id-n].x=cnt;77     }78     build(1,cnt,rt[0]);for(i=1;i<=n;i++)rt[i]=rt[0];79 //  for(i=1;i<=m;i++)if(q[i].id)printf("    %d\n",q[i].x);80     for(i=1;i<=n;i++)for(j=i;j<=n;j+=j&(-j))ins(rt[j],rt[j],1,cnt,b[i]);81     for(i=1;i<=m;i++){82         if(q[i].id){83             run1(q[i].l-1),run2(q[i].r);84     //      printf("    %d--%d       %d %d\n",q[i].l,q[i].r,len1,len2);85     //      for(j=1;j<=len1;j++)printf("  %d",L[j]);puts("!!");for(j=1;j<=len2;j++)printf("  %d",R[j]);puts("");puts("!");86             printf("%d\n",c[query(1,cnt,q[i].x)]);87         }88         else {89             for(j=q[i].l;j<=n;j+=j&(-j))change(rt[j],rt[j],1,cnt,b[q[i].l],1);90             for(j=q[i].l;j<=n;j+=j&(-j))change(rt[j],rt[j],1,cnt,q[i].x,0);91             b[q[i].l]=q[i].x;92         }93     }94     return 0;95 }