主席树其实就是维护$[1,i]$的前缀权值线段树。那么修改一个地方的值$j$，会影响$[1,j]$到$[1,n]$的所有的前缀和，数量级是$O(n)$的，加上维护主席树的$O(log_n)$，就是$O(nlog_n)$，明显不符合复杂度，但是查询却是$O(1)$的，所以无修改的区间第k大用主席树（前缀）就够啦。

对于维护前缀和的东西，一般用树状数组维护起来就能有一个比较漂亮的复杂度了！

那么用树状数组维护这$n$个线段树，每次修改和查询的复杂度都为$O(log^{2}_{n})$，这样$m$次操作的复杂度就为$O(mlog^{2}_{n})$，就够啦！

题目：BZOJ1901 ZJU2112

bzoj需要权限啊TAT

$zju$内存卡这么紧TAT

update: 2015/08/25:Bzoj通过

但是空间$35032kb$好像在$zju$的限制内啊= =

# include <stdio.h>
# include <algorithm>
# include <string.h>
using namespace std;
const int Maxn=100010;
struct segtree {
	int l,r,w;
	segtree() {l=r=w=0;}
}T[21*Maxn];
# define lc(a) T[(a)].l
# define rc(a) T[(a)].r
# define w(a) T[(a)].w
int a[Maxn],t[Maxn*2],tn=0,root[Maxn],P[Maxn],Q[Maxn],K[Maxn];
int n,m;
int size;
char op[Maxn][4];
inline int lb(int x) {return x&(-x);}
void build(int &roots,int l,int r) {
	roots=++size;
	w(roots)=0;
	if(l==r) return;
	int mid=(l+r)>>1;
	build(lc(roots),l,mid);
	build(rc(roots),mid+1,r);
}
void insert(int last,int l,int r,int &roots,int x,int p) {
	roots=++size;
	lc(roots)=lc(last),rc(roots)=rc(last);w(roots)=w(last)+x;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) insert(lc(last),l,mid,lc(roots),x,p);
	else insert(rc(last),mid+1,r,rc(roots),x,p);
}
inline void bitinsert(int x,int num,int del) {
	for (;x<=n;x+=lb(x)) insert(root[x],1,tn,root[x],del,num);
}
int N,M,L[Maxn],R[Maxn];
int query(int l,int r,int k) {
	if(l==r) return l;
	int mid=(l+r)>>1;
	int suma,sumb;
	suma=sumb=0;
	for (int i=1;i<=N;++i) suma+=w(lc(L[i]));
	for (int i=1;i<=M;++i) sumb+=w(lc(R[i]));
	int delta=sumb-suma;
	if(k<=delta) {
		for (int i=1;i<=N;++i) L[i]=lc(L[i]);
		for (int i=1;i<=M;++i) R[i]=lc(R[i]);
		return query(l,mid,k);
	} else {
		for (int i=1;i<=N;++i) L[i]=rc(L[i]);
		for (int i=1;i<=M;++i) R[i]=rc(R[i]);
		return query(mid+1,r,k-delta);	
	}
}
inline int ask(int l,int r,int k) {
	M=N=0;
	for(;l>0;l-=lb(l)) L[++N]=root[l];
	for(;r>0;r-=lb(r)) R[++M]=root[r];
	return query(1,tn,k);
}
int main() {
	int Case;
	scanf("%d",&Case);
	while(Case--) {
		scanf("%d%d",&n,&m);
		size=0;root[0]=0;tn=0;
		memset(t,0,sizeof(t));
		memset(a,0,sizeof(a));
		memset(root,0,sizeof(root));
		for (int i=1;i<=n;++i) {
			scanf("%d",&a[i]);
			t[++tn]=a[i];
		}
		for (int i=1;i<=m;++i) {
			scanf("%s%d%d",op[i],&P[i],&Q[i]);
			if(op[i][0]=='Q') scanf("%d",&K[i]);
			else t[++tn]=Q[i];
		}
		sort(t+1,t+tn+1);
		tn=unique(t+1,t+tn+1)-t-1;
		for (int i=1;i<=n;++i) a[i]=lower_bound(t+1,t+1+tn,a[i])-t;
		build(root[0],1,tn);
		for (int i=1;i<=n;++i) bitinsert(i,a[i],1);
		for (int i=1;i<=m;++i) {
			if(op[i][0]=='Q') {
				printf("%d\n",t[ask(P[i]-1,Q[i],K[i])]);
			} else {
				int pos=lower_bound(t,t+tn+1,Q[i])-t;
				bitinsert(P[i],a[P[i]],-1);
				a[P[i]]=pos;
				bitinsert(P[i],a[P[i]],1);
			}
		}
	}
	return 0;
}