记录编号	357440	评测结果	AAAAAAAAAA
题目名称	2387.[HZOI 2016]2387	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	1.201 s
提交时间	2016-12-11 08:45:52	内存使用	13.28 MiB

#include<map>
#include<vector> 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+100;
const int maxm=maxn*4;
#define LL long long
#define Inf 2e9
#define Begin freopen("2387_.in","r",stdin);freopen("2387_.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
map<int,int> RT;
int size[maxm],ls[maxm],rs[maxm],v[maxm],cnt;
void pushup(int rt){size[rt]=size[ls[rt]]+size[rs[rt]]+1;}
void Turn_right(int & rt){//右旋 
	//把rt的左子树变成左儿子的右子树，rt成为左儿子的右儿子 
	int t=ls[rt];
	ls[rt]=rs[t];pushup(rt);
	rs[t]=rt;pushup(t);
	rt=t; 
}
void Turn_left(int & rt){//左旋 
	//把rt的右子树变成右儿子的左子树，rt成为右儿子的左儿子
	int t=rs[rt];
	rs[rt]=ls[t];pushup(rt);
	ls[t]=rt;pushup(t);
	rt=t;
}

#define Balance_all Balance(rt);Balance(ls[rt]);Balance(rs[rt]);
void Balance(int & rt){
	if(size[ls[ls[rt]]]>size[rs[rt]]){
		Turn_right(rt);Balance_all;return;
	}
	if(size[rs[rs[rt]]]>size[ls[rt]]){
		Turn_left(rt);Balance_all;return;
	}
	if(size[rs[ls[rt]]]>size[rs[rt]]){
		Turn_left(ls[rt]);Turn_right(rt);Balance_all;return;
	}
	if(size[ls[rs[rt]]]>size[ls[rt]]){
		Turn_right(rs[rt]);Turn_left(rt);Balance_all;return;
	}
}
#undef Balance_all

void Del(int & rt,int date){
	if(v[rt]==date){
		if(ls[rt]==0 && rs[rt]==0){rt=0;return;}
		if(ls[rt]==0){rt=rs[rt];return;}
		if(rs[rt]==0){rt=ls[rt];return;}
		Turn_right(rt);Del(rs[rt],date);pushup(rt);
		return;
	}
	if(v[rt]<date)Del(rs[rt],date);
	else Del(ls[rt],date);
	pushup(rt);Balance(rt);
}

void Insert(int & rt,int date){
	if(rt==0){
		rt=++cnt;size[rt]=1;v[rt]=date;return;
	}
	if(date<v[rt])Insert(ls[rt],date);
	else Insert(rs[rt],date);
	pushup(rt);Balance(rt);
}

int Get_date(int rt,int th){
	if(size[ls[rt]]+1==th)return v[rt];
	if(size[ls[rt]]+1>th)return Get_date(ls[rt],th);
	else return Get_date(rs[rt],th-size[ls[rt]]-1);
}
int n,m,XOR,a[maxn];
void Init();

int main(){
	Begin;
	while(scanf("%d%d",&n,&m)!=EOF)Init();
    getchar();getchar();
    End;
	return 0;
}
void Init(){
	memset(size,0,sizeof(size));memset(v,0,sizeof(v));
	memset(ls,0,sizeof(ls));memset(rs,0,sizeof(rs));cnt=0;
	RT.clear();XOR=n;
	for(int i=1;i<=n;i++){
		int x;scanf("%d",&x);a[i]=x;
		Insert(RT[x],i);
	}
	for(int i=1;i<=m;i++){
		char type;int x,k;
		scanf(" %c%d%d",&type,&x,&k);
		if(type=='Q'){
			x^=XOR;k^=XOR;
			if(!RT.count(x) || size[RT[x]]<k){XOR=0;puts("0");}
			else {
				XOR=Get_date(RT[x],k);
				printf("%d\n",XOR);
			}
		}
		else {
			x^=XOR;k^=XOR;
			Del(RT[a[x]],x);
			a[x]=k;
			Insert(RT[k],x);
		}
	}
}