记录编号	490157	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]2387	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	3.049 s
提交时间	2018-03-07 20:42:22	内存使用	62.11 MiB

#include<map>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
using namespace std;
const int maxn=200010;
const int maxm=maxn*20;
int n,m,cnt,las,a[maxn],siz[maxm],ch[maxm][3];
map<int,int>p;
void updata(int x){
	siz[x]=0;
	if(lc(x))siz[x]+=siz[lc(x)];
	if(rc(x))siz[x]+=siz[rc(x)];
}
void insert(int x,int k,int l,int r,int d){
	if(l==r){siz[x]+=d;return;}
	int mid=(l+r)>>1;
	if(k<=mid){
		if(!lc(x))lc(x)=++cnt;
		insert(lc(x),k,l,mid,d);
	}
	else{
		if(!rc(x))rc(x)=++cnt;
		insert(rc(x),k,mid+1,r,d);
	}
	updata(x);
}
int find(int x,int k,int l,int r){
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(lc(x)){
		if(siz[lc(x)]>=k)return find(lc(x),k,l,mid);
		else{k-=siz[lc(x)];return find(rc(x),k,mid+1,r);}
	}
	else return find(rc(x),k,mid+1,r);
}
int main(){
	freopen("2387_.in","r",stdin);
	freopen("2387_.out","w",stdout);
	scanf("%d%d",&n,&m);
	las=n;int x,k;
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		a[i]=x;
		if(!p[x])p[x]=++cnt;
		insert(p[x],i,1,n,1);
	}
	char c[50];
	for(int i=1;i<=m;i++){
		scanf("%s",c);
		if(c[0]=='Q'){
			scanf("%d%d",&x,&k);
			x^=las,k^=las;
			if(!p[x]||siz[p[x]]<k)las=0;
			else las=find(p[x],k,1,n);
			printf("%d\n",las);
		}
		else{
			scanf("%d%d",&k,&x);
			x^=las,k^=las;
			insert(p[a[k]],k,1,n,-1);
			if(!p[x])p[x]=++cnt;
			insert(p[x],k,1,n,1);
			a[k]=x;
		}
	}
	return 0;
}