ZOJ2112 BZOJ1901 Dynamic Rankings 树套树 带修改的区间第k小

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2112

树套树，线段树套splay或者主席树套树状数组，我抄了一下hzwer的代码在zoj上过不了因为zoj的数据比较大不能像hzwer那种写法一样写成nlognlogn的空间。

没有bzoj权限号也不想再写一遍，随便放个代码在这里好惹。

https://www.cnblogs.com/kuangbin/p/3308118.html  <-----这个写法的空间复杂度可以过（就是把树状数组放到外面直接搞），所以ctm我为什么抄hzwer的代码。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 const int maxn=;

 using namespace std;

 char s[]={}; int n,m;

 int val[maxn]={},a[maxn]={},b[maxn]={},k[maxn]={};

 int num[maxn*]={},tot=,flag[maxn]={};

 int sum[maxn*],lc[maxn*],rc[maxn*];

 int rt[maxn]={},siz=;

 int ll[maxn]={},rr[maxn]={},xx,yy;

 void build(int l,int r,int las,int &rot,int z,int v){

     rot=++siz; sum[rot]=sum[las]+v; lc[rot]=lc[las]; rc[rot]=rc[las];

     if(l==r)return;

     int mid=(l+r)/;

     if(z<=mid)build(l,mid,lc[las],lc[rot],z,v);

     else build(mid+,r,rc[las],rc[rot],z,v);

 }

 int query(int l,int r,int z){

     if(l==r)return l;

     int suml=,sumr=;

     for(int i=;i<=xx;i++)suml+=sum[lc[ll[i]]];

     for(int i=;i<=yy;i++)sumr+=sum[lc[rr[i]]];

     int mid=(l+r)/;

     if(sumr-suml>=z){

         for(int i=;i<=xx;i++)ll[i]=lc[ll[i]];

         for(int i=;i<=yy;i++)rr[i]=lc[rr[i]];

         return query(l,mid,z);

     }

     else{

         for(int i=;i<=xx;i++)ll[i]=rc[ll[i]];

         for(int i=;i<=yy;i++)rr[i]=rc[rr[i]];

         return query(mid+,r,z-(sumr-suml));

     }

 }

 int main(){

     int T;scanf("%d",&T);

     while(T-->){

         scanf("%d%d",&n,&m);

         tot=;siz=;

         memset(rt,,sizeof(rt));memset(sum,,sizeof(sum));

         memset(rc,,sizeof(rc));memset(lc,,sizeof(lc));

         memset(flag,,sizeof(flag));

         for(int i=;i<=n;i++){scanf("%d",&val[i]);num[++tot]=val[i];}

         for(int i=;i<=m;i++){

             scanf("%s",s);scanf("%d%d",&a[i],&b[i]);

             if(s[]=='C')num[++tot]=b[i];

             else{scanf("%d",&k[i]);flag[i]=;}

         }

         sort(num+,num+tot+);

         tot=unique(num+,num+tot+)-num-;

         for(int i=;i<=n;i++){

             val[i]=lower_bound(num+,num++tot,val[i])-num;

             for(int j=i;j<=n;j+=(j&-j))

                 build(,tot,rt[j],rt[j],val[i],);

         }

         for(int i=;i<=m;i++){

             if(flag[i]){

                 xx=;yy=;a[i]--;//cout<<a[i]<<b[i]<<endl;

                 for(int j=a[i];j;j-=(j&-j))ll[++xx]=rt[j];

                 for(int j=b[i];j;j-=(j&-j))rr[++yy]=rt[j];

                 printf("%d\n",num[query(,tot,k[i])]);

             }

             else{

                 for(int j=a[i];j<=n;j+=(j&-j))build(,tot,rt[j],rt[j],val[a[i]],-);

                 val[a[i]]=lower_bound(num+,num++tot,b[i])-num;

                 for(int j=a[i];j<=n;j+=(j&-j))build(,tot,rt[j],rt[j],val[a[i]],);

             }

         }

     }

     return ;

 }

并无软用的代码，嘻嘻

所以直接找可持久化线段树的题好了，找主席树出来的都是什么jb。