1901: Zju2112 Dynamic Rankings
Time Limit: 10 Sec Memory Limit: 128 MB Submit: 8107 Solved: 3366 [Submit][Status][Discuss] Description
给定一个含有n个数的序列a[1],a[2],a[3]……a[n]，程序必须回答这样的询问：对于给定的i,j,k，在a[i],a[i+1 ],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改 变后的a继续回答上面的问题。 Input
第一行一个数字N，代表测试组数 对于每组数据第一行有两个正整数n(1≤n≤10000)，m(1≤m≤10000)。 分别表示序列的长度和指令的个数。 第二行有n个数，表示a[1],a[2]……a[n]，这些数都小于10^9。 接下来的m行描述每条指令 每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问a[i]，a[i+1]……a[j]中第k小的数。 C i t (1≤i≤n，0≤t≤10^9)表示把a[i]改变成为t Output
对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。
Sample Input
1
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
Sample Output
3
6
HINT
m,n≤10000。
Source
sol: 树套树裸题
这里简单的聊聊树套树的做法
在外层做一个bit用来维护前缀，里层做一个权值线段树，然后这个实际上就是主席树的思想，一个前缀的权值线段树。对于一个修改，我们修改其在bit上的位置上的权值线段树，这样就修改了所有的前缀。对于一个区间，我们也用前缀表示，那么显而易见的，1到r的数都可以用r的bit上的数表示。那么询问的时候，我们应该把r和l-1的bit抄下来，然后一起走。
#include<cstdio> #include<algorithm> #include<string> #include<cstring> #include<cstdlib> #include<cmath> #include<iostream> using namespace std; int n,m,q,un,vn; inline int read() { char c; int res,flag=0; while((c=getchar())>'9'||c<'0') if(c=='-')flag=1; res=c-'0'; while((c=getchar())>='0'&&c<='9') res=(res<<3)+(res<<1)+c-'0'; return flag?-res:res; } const int N=11000; const int M=1100000; int u[N],v[N]; struct cc { char c; int l,r,k; }a[N]; int val[N],b[M],bn,root[N],lc[M],rc[M],sum[M]; inline int get(int x) { return lower_bound(b+1,b+1+m,x)-b; } int tot; inline void modify(int &k,int l,int r,int x,int v) { if(!k) k=++tot; sum[k]+=v; if(l==r) return; int mid=l+r>>1; if(x<=mid) modify(lc[k],l,mid,x,v); else modify(rc[k],mid+1,r,x,v); } inline void add(int x,int v) { for(int i=x;i<=n;i+=i&-i) modify(root[i],1,m,v,1); } inline void faq(int x,int a,int b) { while(x<=n) { modify(root[x],1,m,a,-1); modify(root[x],1,m,b,1); x+=x&-x; } } inline int query(int l,int r,int k) { if(l==r) return l; int mid=l+r>>1; int ans=0; for(int i=1;i<=un;++i) ans+=sum[lc[u[i]]]; for(int i=1;i<=vn;++i) ans-=sum[lc[v[i]]]; if(ans>=k) { for(int i=1;i<=un;++i) u[i]=lc[u[i]]; for(int i=1;i<=vn;++i) v[i]=lc[v[i]]; return query(l,mid,k); } else { for(int i=1;i<=un;++i) u[i]=rc[u[i]]; for(int i=1;i<=vn;++i) v[i]=rc[v[i]]; return query(mid+1,r,k-ans); } } inline int ask(int l,int r,int k) { int x=l-1; un=vn=0; while(x) {v[++vn]=root[x];x-=x&-x;} x=r; while(x) {u[++un]=root[x];x-=x&-x;} return b[query(1,m,k)]; } char sr[5]; int main() { // freopen("1901.in","r",stdin); // freopen(".out","w",stdout); n=bn=read(); q=read(); for(int i=1;i<=n;++i) val[i]=b[i]=read(); for(int i=1;i<=q;++i) { scanf("%s",sr+1); a[i].c=sr[1]; if(sr[1]=='Q') { a[i].l=read(); a[i].r=read(); a[i].k=read(); } else { a[i].l=read(); a[i].k=read(); b[++bn]=a[i].k; } } sort(b+1,b+1+bn); m=unique(b+1,b+1+bn)-b-1; for(int i=1;i<=n;++i) add(i,get(val[i])); for(int i=1;i<=q;++i) { if(a[i].c=='Q') printf("%d\n",ask(a[i].l,a[i].r,a[i].k)); else { faq(a[i].l,get(val[a[i].l]),get(a[i].k)); val[a[i].l]=a[i].k; } } }