记录编号	120269	评测结果	AAAAAAAAAA
题目名称	动态排名系统	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	2.428 s
提交时间	2014-09-15 21:19:10	内存使用	52.82 MiB

#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int MAXN=50000+10;
char get_char(){
	char x=getchar();
	while(!(x=='Q' || x=='C'))x=getchar();
	return x;
}

struct querys_{
	int a,b,k;
	char op;
	void input(){
		op=get_char();
		if(op=='Q'){
			scanf("%d %d %d",&a,&b,&k);
		}else {
			scanf("%d %d",&a,&b);
		}
	}
}querys[MAXN];

int lowbit(int x){ return x&-x; }
struct node{
	int ls,rs;
	int sum;
}nodes[MAXN*100];
int node_cnt=1;
int arr_tree[MAXN];

int N,M;
int SZ;
int nums[MAXN];
map<int,int> to;

void clear(){
	memset(arr_tree,0,sizeof(arr_tree));
	node_cnt=1;
	N=M=SZ=0;
	memset(nums,0,sizeof(nums));
	to.clear();
}

int creat_node(int ls,int rs,int sum){
	int idx=node_cnt++;
	node & now=nodes[idx];
	now.ls=ls; now.rs=rs; now.sum=sum;
	return idx;
}

void insert_(int & root,int left,int right,int pos,int val){
	if(root==0)root=creat_node(0,0,0);
	node & now=nodes[root];
	now.sum+=val;
	if(left==right)return ;
	int mid=(left+right)/2;
	if(mid>=pos)insert_(now.ls,left,mid,pos,val);
	else insert_(now.rs,mid+1,right,pos,val);
}

void insert(int idx,int pos,int val){
	while(idx<=N){
		insert_(arr_tree[idx],1,SZ,pos,val);
		idx+=lowbit(idx);
	}
}

int query_(vector<int> & root_add,vector<int> & root_del,int left,int right,int k){
	if(left==right)return left;
	
	int sum=0;
	for(int i=0;i<root_add.size();i++){
		//cout<<root_add[i]<<endl;
		//cout<<nodes[root_add[i]].ls<<endl;
		sum+=nodes[ nodes[root_add[i]].ls ].sum;
	}
	for(int i=0;i<root_del.size();i++){
		sum-=nodes[ nodes[root_del[i]].ls ].sum;
	}
	
	int mid=(left+right)/2;
	if(sum>=k){
		for(int i=0;i<root_add.size();i++) root_add[i]=nodes[ root_add[i] ].ls;
		for(int i=0;i<root_del.size();i++) root_del[i]=nodes[ root_del[i] ].ls;
		return query_(root_add,root_del,left,mid,k);
	}else{
		for(int i=0;i<root_add.size();i++) root_add[i]=nodes[ root_add[i] ].rs;
		for(int i=0;i<root_del.size();i++) root_del[i]=nodes[ root_del[i] ].rs;
		return query_(root_add,root_del,mid+1,right,k-sum);
	}
}

int query(int l,int r,int k){
	vector<int> add,del;
	l--;
	while(l){del.push_back(arr_tree[l]);l-=lowbit(l);}
	while(r){add.push_back(arr_tree[r]);r-=lowbit(r);}
	int ret=query_(add,del,1,SZ,k);
	ret=to[ret];
	return ret;
}

void init(){
	scanf("%d %d",&N,&M);
	set<int> num_set;
	SZ=0;
	for(int i=1;i<=N;i++){
		scanf("%d",&nums[i]);
		num_set.insert(nums[i]);
	}
	for(int i=1;i<=M;i++){
		querys[i].input();
		if(querys[i].op=='C'){
			int tmp=querys[i].b;
			num_set.insert(tmp);
		}
	}
	
	map<int,int> m;
	for(set<int>::iterator it=num_set.begin();it!=num_set.end();it++){
		m[*it]=++SZ;
		to[SZ]=(*it);
	}
	
	for(int i=1;i<=N;i++)nums[i]=m[nums[i]];
	for(int i=1;i<=M;i++){
		if(querys[i].op=='C'){
			querys[i].b=m[querys[i].b];
		}
	}
}

void work(){
	for(int i=1;i<=N;i++)insert(i,nums[i],1);
	
	for(int i=1;i<=M;i++){
		querys_ & q=querys[i];
		if(q.op=='Q'){
			int ans=query(q.a,q.b,q.k);
			printf("%d\n",ans);
		}else{
			insert(q.a,nums[q.a],-1);
			nums[q.a]=q.b;
			insert(q.a,nums[q.a],1);
		}
	}
}

int main(){
	//freopen("in.txt","r",stdin);
	freopen("dynrank.in","r",stdin);freopen("dynrank.out","w",stdout);
	int t;scanf("%d",&t);
	for(int i=0;i<t;i++){
		clear();
		init();
		work();
	}
	return 0;
}