Bzoj1901 Zju2112 Dynamic Rankings

树 树套树

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 7419  Solved: 3092

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继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数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。

Input

对于每一次询问，你都需要输出他的答案，每一个输出占单独的一行。

Output

Sample Input

5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output

3

6

HINT

20%的数据中，m,n≤100; 40%的数据中，m,n≤1000; 100%的数据中，m,n≤10000。

Source

树套树

带修改的区间第K大查询。学了树状数组套主席树（跟风）。

线段树+平衡树也能做的吧？

1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<queue>
  6 using namespace std;
  7 const int mxn=200010;
  8 int read(){
  9     int x=0,f=1;char ch=getchar();
 10     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
 11     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
 12     return x*f;
 13 }
 14 int n,m;
 15 struct Que{
 16     int l,r,w;
 17     bool f;
 18 }a[mxn];
 19 int b[mxn],h[mxn];
 20 struct node{
 21     int l,r;
 22     int sum;
 23 }t[mxn*15];
 24 int rot[mxn*15];
 25 int L[mxn],R[mxn];
 26 int cnt=0,nct=0,sz=0;
 27 void insert(int p,int v,int l,int r,int x,int &rt){
 28     rt=++sz;
 29     t[rt]=t[x];//继承结点信息
 30     t[rt].sum+=v;//更新
 31     if(l==r)return;
 32     int mid=(l+r)>>1;
 33     if(p<=mid)insert(p,v,l,mid,t[x].l,t[rt].l);
 34     else insert(p,v,mid+1,r,t[x].r,t[rt].r);
 35     return;
 36 }
 37 void Build(){
 38     for(int i=1;i<=n;i++)
 39         for(int j=i;j<=n;j+=j&-j)
 40             insert(h[i],1,1,cnt,rot[j],rot[j]);
 41     return;
 42 }
 43 int st,ed;
 44 int query(int k,int l,int r){//二分查找 
 45     if(l==r)return l;
 46     int i,suml=0,sumr=0;
 47     for(i=1;i<=st;i++)suml+=t[t[L[i]].l].sum;
 48     for(i=1;i<=ed;i++)sumr+=t[t[R[i]].l].sum;
 49     int mid=(l+r)>>1;
 50     if(sumr-suml>=k){
 51         for(i=1;i<=st;i++)L[i]=t[L[i]].l;
 52         for(i=1;i<=ed;i++)R[i]=t[R[i]].l;
 53         return query(k,l,mid);
 54     }
 55     else{
 56         for(i=1;i<=st;i++)L[i]=t[L[i]].r;
 57         for(i=1;i<=ed;i++)R[i]=t[R[i]].r;
 58         return query(k-(sumr-suml),mid+1,r);
 59     }
 60 }
 61 int main(){
 62     int i,j;
 63     n=read();m=read();
 64     for(i=1;i<=n;i++)b[i]=h[i]=read();
 65     char op[5];
 66     cnt=n;
 67     for(i=1;i<=m;i++){
 68         scanf("%s",op);
 69         if(op[0]=='Q'){
 70             a[i].l=read();a[i].r=read();a[i].w=read();
 71         }
 72         else{
 73             a[i].l=read();a[i].w=read();a[i].f=1;
 74             h[++cnt]=b[cnt]=a[i].w;
 75         }
 76     }
 77     sort(b+1,b+cnt+1);
 78     for(int i=1;i<=cnt;i++)h[i]=lower_bound(b+1,b+cnt+1,h[i])-b;
 79     //
 80     Build();
 81     nct=n;
 82     for(i=1;i<=m;i++){
 83         if(a[i].f){//修改 
 84             nct++;
 85             for(j=a[i].l;j<=n;j+=j&-j){
 86                 insert(h[a[i].l],-1,1,cnt,rot[j],rot[j]);
 87             }
 88 //            h[a[i].l]=a[i].w;× 
 89             h[a[i].l]=h[nct];//更新值
 90             for(j=a[i].l;j<=n;j+=j&-j){
 91                 insert(h[a[i].l],1,1,cnt,rot[j],rot[j]);
 92             } 
 93         }
 94         else{//查询 
 95             st=ed=0;
 96             a[i].l--;
 97             for(j=a[i].l;j;j-=j&-j)L[++st]=rot[j];
 98             for(j=a[i].r;j;j-=j&-j)R[++ed]=rot[j];
 99             int ans=query(a[i].w,1,cnt);
100             printf("%d\n",b[ans]);
101         }
102     }
103     return 0;
104 }      

本文为博主原创文章，转载请注明出处。