1901: Zju2112 Dynamic Rankings - #include <Seter> - using namespace Orz;

1109: [POI2007]堆积木Klo

1901: Zju2112 Dynamic Rankings

Seter posted @ 2012年2月01日 13:16 in BZOJ with tags ChairTree SegTree , 24104 阅读

http://www.zybbs.org/JudgeOnline/problem.php?id=1901

RunID	User	Problem	Result	Memory	Time	Language	Code Length	Submit Time
197772	Seter	1901	Accepted	31456 kb	380 ms	C/Edit	2168 B	2012-02-01 11:05:39

贾教364ms……像个BUG一样……开挂呢罢……我就差重写qsort了……刷不动啊！

首先果断ymFotile……主席树(ChairTree)实在是太神了……

主席树大概是一种离线结构，我以前反正没看到过这东西，所以就自己给他起名字了！如果谁知道这东西的真名，请告诉我！

主席树的主体是线段树，准确的说，是很多棵线段树，存的是一段数字区间出现次数（所以要先离散化可能出现的数字）。

举个例子，假设我每次都要求整个序列内的第k小，那么对整个序列构造一个线段树，然后在线段树上不断找第k小在当前数字区间的左半部分还是右半部分。这个操作和平衡树的Rank操作一样，只是这里将离散的数字搞成了连续的数字。

先假设没有修改操作：

对于每个前缀S1...i，保存这样一个线段树Ti，组成主席树。这样不是会MLE么？最后再讲。

注意，这个线段树对一条线段，保存的是这个数字区间的出现次数，所以是可以互相加减的！还有，由于每棵线段树都要保存同样的数字，所以它们的大小、形态也都是一样的！这实在是两个非常好的性质，是平衡树所不具备的。

对于询问(i,j)，我只要拿出Tj和Ti-1，对每个节点相减就可以了。说的通俗一点，询问i...j区间中，一个数字区间的出现次数时，就是这些数字在Tj中出现的次数减去在 Ti-1中出现的次数。

那么有修改操作怎么办呢？

如果将询问看成求一段序列的数字和，那么上面那个相当于求出了前缀和。加入修改操作后，就要用树状数组等来维护前缀和了。于是那个“很好的性质”又一次发挥了作用，由于主席树可以互相加减，所以可以用树状数组来套上它。做法和维护前缀和长得基本一样，不说了。

开始填坑。由于每棵线段树的大小形态都是一样的，而且初始值全都是0，那每个线段树都初始化不是太浪费了？所以一开始只要建一棵空树即可。

然后是在某棵树上修改一个数字，由于和其他树相关联，所以不能在原来的树上改，必须弄个新的出来。难道要弄一棵新树？不是的，由于一个数字的更改只影响了一条从这个叶子节点到根的路径，所以只要只有这条路径是新的，另外都没有改变。比如对于某个节点，要往右边走，那么左边那些就不用新建，只要用个指针链到原树的此节点左边就可以了，这个步骤的前提也是线段树的形态一样。

假设s是数字个数，这个步骤的空间复杂度显然是O(logs)。用树状数组去套它，共有2logn棵树被修改，m个操作再加上一开始的空树和n个数字，总共就是O((n+m)lognlogs)。Fotile大神说如果加上垃圾回收的话，可以去掉一个log……ym

1901
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56	`#include <stdio.h>` `#include <stdlib.h>` `#define S struct Seg` `#define mid (l+r>>1)` `charsp,str[1000000],p=str;` `int` `n,m,a[20001][2],s,ra[20001],K,Y=1,I,b[20000],v[10001]={-2,-2};` `S{Sc[2];int` `s}R[10001],st[2500000],stp=st,T[10001];` `getint(){` `int` `re=0;` `while(p<'0'\|\|p>'9')p++;` `while(p>='0'&&p<='9')re=re10+p++-48;` `return` `re;` `}cmp(const` `voida,const` `voidb){return(int)b-(int)a;}` `SBuild(l,r){` `Snode=stp++;` `if(l+1!=r)node->c[0]=Build(l,mid),node->c[1]=Build(mid,r);` `return` `node;` `}SSegInsert(x,l,r)Sx;int` `l,r;{` `Snode=stp++;node->s=x->s+Y;` `if(l+1!=r){` `if(I<mid)node->c[1]=x->c[1],node->c[0]=SegInsert(x->c[0],l,mid);` `else` `node->c[0]=x->c[0],node->c[1]=SegInsert(x->c[1],mid,r);` `}return` `node;` `}void` `BitInsert(x){for(;x<=n;x+=x&-x)R[x]=SegInsert(R[x],0,K);}` `void` `Init(x){for(;x;x-=x&-x)if(v[x]!=m)v[x]=m,T[x]=R[x];else` `v[x]=-2;}` `void` `Turn(int` `x,_Bool c){for(;x;x-=x&-x)if(v[x]==m)T[x]=T[x]->c[c];}` `BitQuery(x){int` `ans=0;for(;x;x-=x&-x)if(v[x]==m)ans+=T[x]->c[0]->s;return` `ans;}` `void` `print(x){` `char` `out[10],buf=out;` `if(!x)sp++='0';` `else{` `while(x)buf++=x%10+48,x/=10;` `while(buf--!=out)sp++=buf;` `}sp++='\n';` `}main(){` `int` `i,j,k,re,l,r;fread(p,1,1000000,stdin);` `for(s=n=i=getint(),m=getint();i--;a[i][1]=n-i-1)a[i][0]=getint();` `for(sp=p;p;)if(p++=='C')getint(),a[s][1]=s,a[s++][0]=getint();` `a[a[s][1]=s][0]=ra[s]=-1;` `for(qsort(a,s,8,cmp);s--;b[ra[a[s][1]]=ra[a[s+1][1]]+(a[s][0]!=a[s+1][0])]=a[s][0]);` `for(R[i=1]=Build(0,K=ra[a[0][1]]+1);i++!=n;v[i]=-2)R[i]=R[1];` `for(s=n,p=sp,sp=str,i=-1;++i!=n;BitInsert(i+1))I=ra[i];` `while(m--){` `while(p!='Q'&&p!='C')p++;` `if(p=='Q'){` `i=getint()-1;j=getint();k=getint();` `Init(i);Init(j);l=0;r=K;` `while(l+1!=r)if((re=BitQuery(j)-BitQuery(i))>=k)Turn(i,0),Turn(j,0),r=mid;` `else` `Turn(i,1),Turn(j,1),k-=re,l=mid;` `print(b[l]);` `}else` `if(ra[(i=getint())-1]!=ra[s++]){` `I=ra[i-1];Y=-1;BitInsert(i);` `I=ra[i-1]=ra[s-1];Y=1;BitInsert(i);` `}` `}fwrite(str,1,sp-str,stdout);return` `0;` `}`