记录编号	89017	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.874 s
提交时间	2014-02-27 18:38:08	内存使用	192.17 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
const int SIZEN=100100,SIZEM=11000;
const int SIZENODE=SIZEN*100;
int N,M;
class FSEG{
public:
	int sum;
	int l,r;
	int lson,rson;
	FSEG(){sum=0;l=r=0;lson=rson=-1;}
};
FSEG ftree[SIZENODE];
int tot=0;
int build(int left,int right){
	if(left>right) return -1;
	int x=tot++;
	ftree[x].l=left,ftree[x].r=right;
	if(right>left){
		int mid=(left+right)>>1;
		ftree[x].lson=build(left,mid);
		ftree[x].rson=build(mid+1,right);
	}
	return x;
}
int change(int p,int x,int t){//在p为根的子树中,节点x加上t
	int root=tot++;
	ftree[root]=ftree[p];//新开一个节点,先复制
	ftree[root].sum+=t;
	if(ftree[root].l==x&&ftree[root].r==x) return root;
	int mid=(ftree[root].l+ftree[root].r)>>1;
	if(x<=mid) ftree[root].lson=change(ftree[root].lson,x,t);//改左节点
	else ftree[root].rson=change(ftree[root].rson,x,t);//改右节点
	return root;
}
class REQUEST{
public:
	char cmd;
	int l,r,k;
};
int cmroot[SIZEN]={0};//外层的树状数组
int A[SIZEN]={0};//初始数据和排序后的所有数
vector<int> avail;
REQUEST req[SIZEM];
int lowbit(int x){
	return x&(-x);
}
void cmchange(int tax,int stx,int t){//树状数组的代表的元素tax中线段树代表的元素stx+=t
	for(int i=tax;i<=avail.size();i+=lowbit(i)) cmroot[i]=change(cmroot[i],stx,t);
}
int lsonsum(vector<int> &ft){//ft中树的左儿子和
	int ans=0;
	for(int i=0;i<ft.size();i++) ans+=ftree[ftree[ft[i]].lson].sum;
	return ans;
}
void goleft(vector<int> &ft){
	for(int i=0;i<ft.size();i++) ft[i]=ftree[ft[i]].lson;
}
void goright(vector<int> &ft){
	for(int i=0;i<ft.size();i++) ft[i]=ftree[ft[i]].rson;
}
int query(vector<int> &lft,vector<int> &rft,int k){//rft-left中所有树之并中的第k个树
	if(ftree[rft[0]].l==ftree[rft[0]].r) return ftree[rft[0]].l;
	int now=lsonsum(rft)-lsonsum(lft);
	if(k<=now){
		goleft(lft);goleft(rft);
		return query(lft,rft,k);
	}
	else{
		goright(lft);goright(rft);
		return query(lft,rft,k-now);
	}
}
int query(int l,int r,int k){
	vector<int> latp,ratp;
	for(int i=l-1;i>0;i-=lowbit(i)) latp.push_back(cmroot[i]);
	for(int i=r;i>0;i-=lowbit(i)) ratp.push_back(cmroot[i]);
	return query(latp,ratp,k);
}
void makecmtree(void){
	cmroot[0]=build(1,avail.size());
	for(int i=1;i<=avail.size();i++) cmroot[i]=cmroot[0];
	for(int i=1;i<=N;i++) cmchange(i,A[i],1);
}
int hash(int x){//找到x在排好序的数组s中是第几个
	return lower_bound(avail.begin(),avail.end(),x)-avail.begin()+1;
}
void work(void){
	for(int i=1;i<=M;i++){
		if(req[i].cmd=='Q') printf("%d\n",avail[query(req[i].l,req[i].r,req[i].k)-1]);
		else if(req[i].cmd=='C'){
			cmchange(req[i].l,A[req[i].l],-1);
			cmchange(req[i].l,req[i].k,1);
			A[req[i].l]=req[i].k;
		}
	}
}
void globalclear(void){
	memset(req,0,sizeof(req));
	memset(A,0,sizeof(A));
	avail.clear();
	memset(cmroot,0,sizeof(cmroot));
	tot=0;
}
void init(void){
	scanf("%d%d",&N,&M);
	vector<int> atp;
	for(int i=1;i<=N;i++) scanf("%d",&A[i]),atp.push_back(A[i]);
	for(int i=1;i<=M;i++){
		cin>>req[i].cmd;
		if(req[i].cmd=='Q')	scanf("%d%d%d",&req[i].l,&req[i].r,&req[i].k);
		else if(req[i].cmd=='C'){
			scanf("%d%d",&req[i].l,&req[i].k);
			atp.push_back(req[i].k);
		}
	}
	sort(atp.begin(),atp.end());
	for(int i=0;i<atp.size();i++) if(!i||atp[i]!=atp[i-1]) avail.push_back(atp[i]);
	for(int i=1;i<=N;i++) A[i]=hash(A[i]);
	for(int i=1;i<=M;i++) if(req[i].cmd=='C') req[i].k=hash(req[i].k);
}
int main(){
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout);
	int T;scanf("%d",&T);
	while(T--){
		globalclear();
		init();
		makecmtree();
		work();
	}
	return 0;
}