记录编号	294322	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	9.260 s
提交时间	2016-08-11 21:18:33	内存使用	3.30 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

struct _node{
	_node *lc,*rc;
	int l,r,nl,nr;
	_node(){
		lc=rc=0;l=r=nl=nr=0;
	}
	_node(int a,int b):l(a),r(b){
		nl=nr=0;lc=rc=0;
	}
};
class function_segment_tree{
	void build(_node *x){
		if (x->l==x->r) return;
		int m=(x->l+x->r)/2;
		x->lc=new _node(x->l,m);
		x->rc=new _node(m+1,x->r);
		build(x->lc);build(x->rc);
	}
	void insert(_node *now,_node *last,int y){
		*now=*last;
		if (now->l==now->r) return;
		int m=(now->l+now->r)/2;
		if (y>m){
			now->nr++;now->rc=new _node();
			insert(now->rc,last->rc,y);
		}
		else{
			now->nl++;now->lc=new _node();
			insert(now->lc,last->lc,y);
		}
	}
	void change(_node *now,_node *last,int x,int add){
		*now=*last;
		if (now->l==now->r) return;
		int m=(now->l+now->r)/2;
		if (x>m){
			now->nr+=add;now->rc=new _node();
			change(now->rc,last->rc,x,add);
		}
		else{
			now->nl+=add;now->lc=new _node();
			change(now->lc,last->lc,x,add);
		}
	}
public:
	_node *root,*last;
	function_segment_tree(){}
	function_segment_tree(int _left,int _right){
		root=new _node(_left,_right);
		build(root);
	}
	void clear(){
		delete root;
	}
	void insert(int x){
		last=root;
		root=new _node();
		insert(root,last,x);
	}
	void change(int x,int add){
		last=root;
		root=new _node();
		change(root,last,x,add);
	}
};

const int N=100010;
int cas,cnt,n,m,i,j,a[N],A[N];
int find(int x,int l,int r){
	if (l==r) return l;
	int m=(l+r)/2;
	return x<=A[m]?find(x,l,m):find(x,m+1,r);
}
int lowbit(int x){
	return x&(-x);
}
struct ques{
	char ch;int i,j,k;
}Q[N];
function_segment_tree T[N];
_node *le[N],*ri[N],*p;
int sl,sr;
int ask(int l,int r,int k){
	sl=sr=0;l--;
	for (;l;l-=lowbit(l)) le[++sl]=T[l].root;
	for (;r;r-=lowbit(r)) ri[++sr]=T[r].root;
	p=T[0].root;
	while (1){
		if (p->l==p->r) return p->l;
		int nl=0;
		for (int i=1;i<=sl;i++) nl-=le[i]->nl;
		for (int i=1;i<=sr;i++) nl+=ri[i]->nl;
		if (k>nl){
			k-=nl;p=p->rc;
			for (int i=1;i<=sl;i++) le[i]=le[i]->rc;
			for (int i=1;i<=sr;i++) ri[i]=ri[i]->rc;
		}
		else{
			p=p->lc;
			for (int i=1;i<=sl;i++) le[i]=le[i]->lc;
			for (int i=1;i<=sr;i++) ri[i]=ri[i]->lc;
		}
	}
}
/*void bianli(_node *x){
	if (x->l==x->r){
		printf("%d ",x->l);return;
	}
	if (x->nl) bianli(x->lc);
	if (x->nr) bianli(x->rc);
}*/

int main()
{
	freopen("dynrank.in","r",stdin);
	freopen("dynrank.out","w",stdout); 
	scanf("%d",&cas);
	while (cas--){
		scanf("%d%d",&n,&m);
		for (int i=1;i<=n;i++)
			T[i].clear();
		for (int i=1;i<=n;i++)
			scanf("%d",&a[i]),A[i]=a[i];
		cnt=n;
		for (int i=1;i<=m;i++){
			scanf("%s%d%d",&Q[i].ch,&Q[i].i,&Q[i].j);
			if (Q[i].ch=='Q') scanf("%d",&Q[i].k);
				else A[++cnt]=Q[i].j;
		}
		sort(A+1,A+cnt+1);
		for (int i=1;i<=n;i++)
			a[i]=find(a[i],1,cnt);
		for (int i=1;i<=m;i++)
		if (Q[i].ch=='C')
			Q[i].j=find(Q[i].j,1,cnt);
		T[0]=function_segment_tree(1,cnt);
		for (int i=1;i<=n;i++)
			T[i].root=T[0].root;
		for (int i=1;i<=n;i++)
		for (int j=i;j<=n;j+=lowbit(j))
			T[j].insert(a[i]);
		for (int i=1;i<=m;i++){
			if (Q[i].ch=='C'){
				for (int j=Q[i].i;j<=n;j+=lowbit(j))
					T[j].change(a[Q[i].i],-1),T[j].change(Q[i].j,1);
				a[Q[i].i]=Q[i].j;
			}
			else printf("%d\n",A[ask(Q[i].i,Q[i].j,Q[i].k)]);
		}
	}
	return 0;
}