zoj 2112 Dynamic Rankings (主席树+树状数组)

题意：

思路：

     动态区间第k大，我用的是主席树+树状数组，这个不是最优解，因为空间很吃紧，正解应该是整体二分，CDQ分治什么的，然而现在不会，会了补上写法
     那么我们来说一下怎么用主席树过，首先我们发现，假如我们改变了x，那么对应就影响了x,x+1,x+2,…..n这几颗树，暴力地每个开一个时间空间都不允许，那么我们可以用树状数组记录，因为树状数组向上跳的过程是logn的，我们每个树开的空间也是$logn$的，所以空间复杂度就是$O(nlogn+mlognlogn)$，时间复杂度是$O(nlogn+mlognlogn)$这个我们很明显是能够接受的，如果我们把某个节点由x变成y，那么我们新建立的树，减x加y，这样就能维护变化了，到了最后统计的时候，静态的主席树+变化值就是现在的值。
     总结一下，首先我们和静态一样，先建立主席树，然后开一个数组，让这个数组和树状数组一样向上跳，每个节点维护的是根节点，然后统计的时候，在静态基础上加上树状数组统计的变化即可，因为树状数组只是维护的根节点，当我们需要统计某一层的时候，就不知道位置了，就需要use数组记录，每次不断更新use数组即可。
     你可能会说，这样use数组不会出现重叠部分吗？会，但是因为我们要的是u到v部分，产生的重叠部分已经减去了，所以最后结果还是对的

错误及反思：

空间需要40倍。。。use数组是看了别人的博客才学会的。。。

代码：

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define lson l,m
#define rson m+1,r
const int N = 50100;
int sum[40*N],ls[N*40],rs[N*40],a[N],root[N],cnt,n,que,T,bit[N],use[N];
vector<int> v;
struct Q{bool k; int l,r,d;
}q[10100];int getid(int x){
   return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}void init(){cnt=0; v.clear();
}int build(int l,int r){int rt=++cnt;ls[rt]=rt,rs[rt]=rt,sum[rt]=0;if(l==r) return rt;int m=(l+r)/2;ls[rt]=build(lson);rs[rt]=build(rson);return rt;
}int update(int pre,int x,int val,int l,int r){int rt=++cnt;ls[rt]=ls[pre],rs[rt]=rs[pre],sum[rt]=sum[pre]+val;if(l==r) return rt;int m=(l+r)/2;if(x<=m) ls[rt]=update(ls[pre],x,val,lson);else rs[rt]=update(rs[pre],x,val,rson);return rt;
}int Sum(int x){int ret=0;while(x){ret+=sum[ls[use[x]]];x-=x&-x;}return ret;
}void add(int x,int p,int d){while(x<=n){bit[x]=update(bit[x],p,d,1,v.size());x+=x&-x;}
}int query(int u, int v, int lr, int rr, int l, int r, int k){if(l==r) return l;int m=(l+r)>>1;int tmp=Sum(v)-Sum(u)+sum[ls[rr]]-sum[ls[lr]];if(tmp>=k){for(int i=u;i;i-=i&-i)use[i]=ls[use[i]];for(int i=v;i;i-=i&-i)use[i]=ls[use[i]];return query(u, v, ls[lr], ls[rr], lson, k);}else{for(int i=u;i;i-=i&-i)use[i]=rs[use[i]];for(int i=v;i;i-=i&-i)use[i]=rs[use[i]];return query(u, v, rs[lr], rs[rr], rson, k-tmp);}
}int main(){scanf("%d",&T);while(T--){init();scanf("%d%d",&n,&que);for(int i=1;i<=n;i++){scanf("%d",&a[i]);v.push_back(a[i]);}for(int i=1;i<=que;i++){char ta[10]; scanf("%s",ta);if(ta[0]=='C'){int l,r; scanf("%d%d",&l,&r);q[i].k=0; q[i].l=l; q[i].d=r;v.push_back(r);}else{int l,r,k; scanf("%d%d%d",&l,&r,&k);q[i].k=1; q[i].l=l; q[i].r=r; q[i].d=k;}}sort(v.begin(),v.end()),v.erase(unique(v.begin(),v.end()),v.end());root[0]=build(1,v.size());for(int i=1;i<=n;i++) root[i]=update(root[i-1],getid(a[i]),1,1,v.size());for(int i=1;i<=n;i++) bit[i]=root[0];for(int i=1;i<=que;i++){if(q[i].k){for(int j=q[i].l-1;j;j-=j&-j) use[j]=bit[j];for(int j=q[i].r;j;j-=j&-j) use[j]=bit[j];printf("%d\n",v[query(q[i].l-1,q[i].r,root[q[i].l-1],root[q[i].r],1,v.size(),q[i].d)-1]);}else{add(q[i].l,getid(a[q[i].l]),-1);add(q[i].l,getid(q[i].d),1);a[q[i].l]=q[i].d;}}}
}