记录编号	146651	评测结果	AEEEEEAAEE
题目名称	动态排名系统	最终得分	30
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	0.508 s
提交时间	2015-01-18 17:29:53	内存使用	0.50 MiB

#include<cstdio>
using namespace std;
typedef class SBT_T* SBT;
const int N = 10010;
const int INF = 1000000010;
struct SBT_T{
	int key,siz;
	SBT c[2];
	SBT_T(){key=0;siz=0;c[1]=NULL;c[0]=NULL;}
};
SBT T[N<<2];
int DD,n,m,M,a[N],ne,la,tim=0;
void Get(int &x){
	x=0;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar());
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-48;
}
int Siz(SBT o){if(o==NULL) return 0;return o->siz;}
SBT Gch(SBT o,bool c1,bool c2){if(o->c[c1]==NULL) return NULL;return o->c[c1]->c[c2];}
void Rot(SBT &o,bool f){
	SBT t=o->c[!f];
	if(t==NULL) t=new SBT_T;
	if(t->c[f]==NULL) t->c[f]=new SBT_T;
	o->c[!f]=t->c[f];
	t->c[f]=o;
	t->siz=Siz(o);
	o->siz=Siz(o->c[0])+Siz(o->c[1])+1;
	o=t;
	return;
}
void Maintain(SBT &o,bool f){
	if(Siz(o)<=1) return;
	if(Siz(Gch(o,f,f)) > Siz(o->c[!f])) Rot(o,!f);
	else if(Siz(Gch(o,f,!f)) > Siz(o->c[!f])) Rot(o->c[f],f),Rot(o,!f);
	else return;
	Maintain(o->c[0],0);
	Maintain(o->c[1],1);
	Maintain(o,0);
	Maintain(o,1);return;
}
void Insert(SBT &o,int x){
	if(Siz(o)==0){
		if(o==NULL) o=new SBT_T;
		o->key=x;o->siz=1;
		return;
	}
	o->siz++;
	bool f=(x>=o->key);
	Insert(o->c[f],x);
	Maintain(o,f);
	return;
}
void Delete(SBT &o,int x){
	if(Siz(o)==0) return;
	if(o->key==x){
		if(Siz(o->c[0])==0){o=o->c[1];return;}
		if(Siz(o->c[1])==0){o=o->c[0];return;}
		SBT t=o->c[0];
		while(Siz(t->c[1])) t=t->c[1];
		o->key=t->key;
		o->siz--;
		Delete(o->c[0],o->key);
		return;
	}
	o->siz--;
	Delete(o->c[(x>=o->key)],x);
	return;
}
int Rank(SBT o,int x){
	int ran=0;
	while(Siz(o)){
		if(o->key < x) ran+=Siz(o->c[0])+1,o=o->c[1];
		else o=o->c[0];
	}
	return ran;
}
void Join(SBT o,SBT &p){
	if(Siz(o)>0){
		Insert(p,o->key);
		Join(o->c[0],p);
		Join(o->c[1],p);
	}
	return;
}
int R_Rank(int x,int y,int xx){
	int res=0;
	for(x=x+M-1,y=y+M+1;x^y^1;x>>=1,y>>=1){
		if(~x&1) res+=Rank(T[x^1],xx);
		if( y&1) res+=Rank(T[y^1],xx);
	}
	return res+1;
}
void Find_Kth(int x,int y,int xx){
	int l=0,r=INF,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(R_Rank(x,y,mid)<=xx) l=mid+1,ans=mid;
		else r=mid-1;
	}
	printf("%d\n",ans);
	return;
}
void Change(int x){
	x+=M;
	Insert(T[x],ne);Delete(T[x],la);
	for(x>>=1;x;x>>=1) Insert(T[x],ne),Delete(T[x],la);
	return;
}
void Print(SBT o){
	if(Siz(o)==0) return;
	Print(o->c[0]);
	printf("%d ",o->key);
	Print(o->c[1]);
}
void Print_Tree(int x){
	printf("now=%d:",x);
	Print(T[x]);
	printf("\n");
}
void Delete_Tree(SBT &o){
	if(Siz(o)==0) return;
	Delete_Tree(o->c[0]);
	Delete_Tree(o->c[1]);
	o=NULL;
}
void Doit(){
	Get(n);Get(m);
	for(M=1;M<=n;M<<=1);
	for(int i=1;i<=(M<<1)+1;i++) T[i]=NULL;
	for(int i=1;i<=n;i++) Get(a[i]);
	for(int i=1;i<=n;i++) Insert(T[i+M],a[i]);
	for(int i=M-1;i>=1;i--)
		Join(T[i<<1],T[i]),Join(T[i<<1|1],T[i]);
	char typ[10];int x,y,z;
	while(m--){
		scanf("%s",typ);
		if(typ[0]=='C'){
			Get(x),Get(y);
			ne=y;la=a[x];a[x]=ne;
			Change(x);
		}
		else Get(x),Get(y),Get(z),Find_Kth(x,y,z);
	}
	for(int i=1;i<=(M<<1)+1;i++) Delete_Tree(T[i]); 
}
int main(){
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	Get(DD);
	while(DD--) Doit();
	return 0;
}