记录编号	366341	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]2387	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.623 s
提交时间	2017-01-23 17:19:05	内存使用	1.07 MiB

#include<cstdio>
#include<algorithm>
#include<map>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_mapped_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> Tree;
map<int,Tree> M;
const int N=2e5+10;
int n,q,x,k,a[N],ans;char ch[5];
int main()
{
	freopen("2387_.in","r",stdin);
	freopen("2387_.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		M[a[i]].insert(i);
	}
	ans=n;
	while (q--){
		scanf("%s%d%d",ch,&x,&k);
		x^=ans;k^=ans;
		if (ch[0]=='M'){
			M[a[x]].erase(x);
			M[k].insert(x);
			a[x]=k;
		}
		else printf("%d\n",ans=*M[x].find_by_order(k-1));
	}
	return 0;
}