高级数据结构(树状数组套主席树)：ZOJ 2112 Dynamic Rankings

Dynamic Rankings

Time Limit: 10 Seconds Memory Limit: 32768 KB

The Company Dynamic Rankings has developed a new kind of computer that is no longer satisfied with the query like to simply find the k-th smallest number of the given N numbers. They have developed a more powerful system such that for N numbers a[1], a[2], ..., a[N], you can ask it like: what is the k-th smallest number of a[i], a[i+1], ..., a[j]? (For some i<=j, 0<k<=j+1-i that you have given to it). More powerful, you can even change the value of some a[i], and continue to query, all the same.

Your task is to write a program for this computer, which

- Reads N numbers from the input (1 <= N <= 50,000)

- Processes M instructions of the input (1 <= M <= 10,000). These instructions
include querying the k-th smallest number of a[i], a[i+1], ..., a[j] and change
some a[i] to t.

Input

The first line of the input is a single number X (0 < X <= 4), the number
of the test cases of the input. Then X blocks each represent a single test case.

The first line of each block contains two integers N and M, representing N numbers
and M instruction. It is followed by N lines. The (i+1)-th line represents the
number a[i]. Then M lines that is in the following format

Q i j k or
C i t

It represents to query the k-th number of a[i], a[i+1], ..., a[j] and change
some a[i] to t, respectively. It is guaranteed that at any time of the operation.
Any number a[i] is a non-negative integer that is less than 1,000,000,000.

There're NO breakline between two continuous test cases.

Output

For each querying operation, output one integer to represent the result. (i.e.
the k-th smallest number of a[i], a[i+1],..., a[j])

There're NO breakline between two continuous test cases.

Sample Input

2
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3
5 3
3 2 1 4 7
Q 1 4 3
C 2 6
Q 2 5 3

Sample Output

3
6
3
6

　　不知道为何，ZOJ上交这道题要FQ，BZOJ上有这道题，还TM是权限题，估计是偷的（鄙视BZOJ）。

　　因为有修改操作，考虑保持原有的主席树结构，假设i位置上的数变化，那么要修改主席树中i及i以后的位置，如果一个一个修改肯定超时，可以考虑将修改的时间摊到查询上去，用Bit维护修改操作，记为前缀和，很好脑补。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int maxn=;

 const int maxm=;

 int tot,cnt,hash[maxn],a[maxn];

 int sum[maxm],ch[maxm][],rt[maxn],bit[maxn];

 int use[maxn],n;

 struct Ask{

     int l,r,k;

 }q[maxn];

 void Insert(int pre,int &rt,int l,int r,int g,int d){

     rt=++cnt;

     ch[rt][]=ch[pre][];

     ch[rt][]=ch[pre][];

     sum[rt]=sum[pre]+d;

     if(l==r)return;

     int mid=(l+r)>>;

     if(mid>=g)Insert(ch[pre][],ch[rt][],l,mid,g,d);

     else Insert(ch[pre][],ch[rt][],mid+,r,g,d);

 }

 void Modify(int p,int g,int d){

     while(p<=n){

         Insert(bit[p],bit[p],,tot,g,d);

         p+=p&(-p);

     }

 }

 int Query(int pre,int rt,int l,int r,int k,int L,int R){

     if(l==r)return l;

     int mid=(l+r)>>,p=R,c=;

     while(p){c+=sum[ch[use[p]][]];p-=p&(-p);}p=L-;

     while(p){c-=sum[ch[use[p]][]];p-=p&(-p);}

     c+=sum[ch[rt][]]-sum[ch[pre][]];

     if(c>=k){

         p=R;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}p=L-;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}

         return Query(ch[pre][],ch[rt][],l,mid,k,L,R);

     }

     else{

         k-=c;p=R;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}p=L-;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}

         return Query(ch[pre][],ch[rt][],mid+,r,k,L,R);

     }

 }

 int Solve(int l,int r,int k){

     int p=l-;

     while(p){use[p]=bit[p];p-=p&(-p);}p=r;

     while(p){use[p]=bit[p];p-=p&(-p);}

     return Query(rt[l-],rt[r],,tot,k,l,r);

 }

 void Init(){

     memset(rt,,sizeof(rt));cnt=;

     memset(bit,,sizeof(bit));

 }

 bool cmp(int a,int b){

     return a>b;

 }

 char op[];

 int main(){

     int T,Q;

     scanf("%d",&T);

     while(T--){

         Init();

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

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

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

         tot=n;

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

             scanf("%s",op);

             if(op[]=='Q')

                 scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].k);

             else{

                 scanf("%d%d",&q[i].l,&q[i].k);

                 a[++tot]=q[i].k;q[i].r=-;

             }

         }

         for(int i=;i<=tot;i++)

             hash[i]=a[i];

         sort(hash+,hash+tot+);

         for(int i=;i<=tot;i++)

             a[i]=lower_bound(hash+,hash+tot+,a[i])-hash;    

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

             Insert(rt[i-],rt[i],,tot,a[i],);

         for(int i=,head=n;i<=Q;i++){

             if(q[i].r==-){

                 Modify(q[i].l,a[q[i].l],-);

                 Modify(q[i].l,a[++head],);

                 a[q[i].l]=a[head];

             }

             else

                 printf("%d\n",hash[Solve(q[i].l,q[i].r,q[i].k)]);

         }

     }

     return ;

 }

2016年6月9日重打了一遍……

 #include <algorithm>

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 const int maxm=;

 char op[];

 int n,Q,T,use[maxn];

 int qa[maxn],qb[maxn],qk[maxn];

 int tot,cnt,ch[maxm][],sum[maxm];

 int a[maxn],hash[maxn],bit[maxn],rt[maxn];

 void Insert(int pre,int &rt,int l,int r,int g,int d){

     rt=++cnt;

     ch[rt][]=ch[pre][];

     ch[rt][]=ch[pre][];

     sum[rt]=sum[pre]+d;

     if(l==r)return;

     if(l+r>>>=g)Insert(ch[pre][],ch[rt][],l,l+r>>,g,d);

     else Insert(ch[pre][],ch[rt][],(l+r>>)+,r,g,d);

 }

 void Modify(int p,int g,int d){

     while(p<=n){

         Insert(bit[p],bit[p],,tot,g,d);

         p+=p&(-p);

     }

 }

 int Query(int pre,int rt,int l,int r,int k,int L,int R){

     if(l==r)return l;

     int c=sum[ch[rt][]]-sum[ch[pre][]],p=R;

     while(p){c+=sum[ch[use[p]][]];p-=p&(-p);}p=L-;

     while(p){c-=sum[ch[use[p]][]];p-=p&(-p);}

     if(c>=k){p=R;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}p=L-;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}

         return Query(ch[pre][],ch[rt][],l,l+r>>,k,L,R);

     }

     else{p=R;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}p=L-;

         while(p){use[p]=ch[use[p]][];p-=p&(-p);}

         return Query(ch[pre][],ch[rt][],(l+r>>)+,r,k-c,L,R);

     }

 }

 int Solve(int i){

     int p=qb[i];

     while(p){use[p]=bit[p];p-=p&(-p);}p=qa[i]-;

     while(p){use[p]=bit[p];p-=p&(-p);}

     return Query(rt[qa[i]-],rt[qb[i]],,tot,qk[i],qa[i],qb[i]);

 }

 void Init(){

     memset(bit,,sizeof(bit));

     cnt=;tot=n;

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("dynrank.in","r",stdin);

     freopen("dynrank.out","w",stdout);

 #endif

     scanf("%d",&T);

     while(T--){

         scanf("%d%d",&n,&Q);Init();

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

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

             hash[i]=a[i];

         }

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

             scanf("%s",op);

             if(op[]=='Q')scanf("%d%d%d",&qa[i],&qb[i],&qk[i]);

             else{

                 scanf("%d%d",&qa[i],&qk[i]);

                 tot++;hash[tot]=a[tot]=qk[i];qb[i]=-;

             }

         }

         sort(hash+,hash+tot+);

         for(int i=;i<=tot;i++)

             a[i]=lower_bound(hash+,hash+tot+,a[i])-hash;

         for(int i=;i<=n;i++)Insert(rt[i-],rt[i],,tot,a[i],);

         for(int i=,p=n;i<=Q;i++){

             if(qb[i]==-){

                 Modify(qa[i],a[qa[i]],-);

                 Modify(qa[i],a[++p],);

                 a[qa[i]]=a[p];

             }

             else

                 printf("%d\n",hash[Solve(i)]);

         }

     }

     return ;

 }

　　还打了一个强大的整体二分。

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 int T,n,Q,cntQ;

 int num[maxn],ans[maxn],bit[maxn];

 char op[];

 struct Node{

     int x,y,k,id,tp;

 }a[maxn],t1[maxn],t2[maxn];

 //tp==1 add; tp==2 del; tp==3 query;

 void Add(int x,int d){

     while(x<=n){

         bit[x]+=d;

         x+=x&(-x);

     }

 }

 int Query(int x){

     int ret=;

     while(x){

         ret+=bit[x];

         x-=x&(-x);

     }

     return ret;

 }

 void Solve(int h,int t,int l,int r){

     if(l==r){

         for(int i=h;i<=t;i++)

             if(a[i].tp==)ans[a[i].id]=l;

         return;

     }

     if(h>t)return;

     int p1=,p2=,d;

     for(int i=h;i<=t;i++){

         if(a[i].tp==){

             d=Query(a[i].y)-Query(a[i].x-);

             if(d>=a[i].k)t1[++p1]=a[i];

             else{

                 a[i].k-=d;

                 t2[++p2]=a[i];

             }

         }

         else if(a[i].k<=l+r>>){

             if(a[i].tp==)Add(a[i].x,);

             if(a[i].tp==)Add(a[i].x,-);

             t1[++p1]=a[i];

         }

         else t2[++p2]=a[i];

     }

     for(int i=h;i<=t;i++){

         if(a[i].k<=l+r>>){

             if(a[i].tp==)Add(a[i].x,-);

             if(a[i].tp==)Add(a[i].x,);

         }

     }

     for(int i=;i<=p1;i++)a[h+i-]=t1[i];

     for(int i=;i<=p2;i++)a[h+i+p1-]=t2[i];

     Solve(h,h+p1-,l,l+r>>);

     Solve(h+p1,t,(l+r>>)+,r);

 }

 int main(){

 #ifndef ONLINE_JUDGE

     freopen("dynrank.in","r",stdin);

     freopen("dynrank.out","w",stdout);

 #endif

     scanf("%d",&T);

     while(T--){

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

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

             scanf("%d",&a[i].k);

             a[i].x=i;a[i].tp=;

             num[i]=a[i].k;

         }

         cntQ=;

         int x,y,k;

         while(Q--){

             scanf("%s",op);

             if(op[]=='Q'){

                 scanf("%d%d%d",&x,&y,&k);

                 a[++n].id=++cntQ;a[n].tp=;

                 a[n].x=x;a[n].y=y;a[n].k=k;

             }

             else{

                 scanf("%d%d",&x,&k);

                 a[++n].tp=;a[n].x=x;a[n].k=num[x];

                 a[++n].tp=;a[n].x=x;a[n].k=k;num[x]=k;

             }

         }

         Solve(,n,,);

         for(int i=;i<=cntQ;i++)

             printf("%d\n",ans[i]);

     }

     return ;

 }

巴特西

高级数据结构(树状数组套主席树)：ZOJ 2112 Dynamic Rankings

最新文章

热门文章