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

贾教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

#include <stdio.h>
#include <stdlib.h>
#define S struct Seg
#define mid (l+r>>1)
char*sp,str[1000000],*p=str;
int n,m,a[20001][2],s,ra[20001],K,Y=1,I,b[20000],v[10001]={-2,-2};
S{S*c[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=re*10+*p++-48;
	return re;
}cmp(const void*a,const void*b){return*(int*)b-*(int*)a;}
S*Build(l,r){
	S*node=stp++;
	if(l+1!=r)node->c[0]=Build(l,mid),node->c[1]=Build(mid,r);
	return node;
}S*SegInsert(x,l,r)S*x;int l,r;{
	S*node=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;
}

• inline
• block