记录编号	483543	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.718 s
提交时间	2018-01-17 18:56:11	内存使用	24.73 MiB

#include<bits/stdc++.h>
#define MAXN 100010
#define lc(x) t[x].l
#define rc(x) t[x].r
namespace IO{
	inline int qr(){
		int x=0,rev=0,ch=getchar();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=getchar();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
		return rev?-x:x;}
}using namespace IO;
using namespace std;
struct Note{
	int v,l,r;
}t[MAXN*20];
int N,M,Q,tot,root[MAXN],id[MAXN],f[MAXN],a[MAXN];
int findf(int x){return x==f[x]? f[x]:f[x]=findf(f[x]);}
void Insert(int p,int l,int r,int &rt){
	if(!rt)rt=++tot;
	if(l==r){t[rt].v++;return;}
	int mid=l+r>>1;
	if(p<=mid)Insert(p,l,mid,lc(rt));
	else Insert(p,mid+1,r,rc(rt));
	t[rt].v=t[lc(rt)].v+t[rc(rt)].v;
}
int Merge(int x,int y){
	if(!x||!y)return x^y;
	lc(x)=Merge(lc(x),lc(y));
	rc(x)=Merge(rc(x),rc(y));
	t[x].v=t[lc(x)].v+t[rc(x)].v;
	return x;
}
int Query(int rt,int l,int r,int k){
	if(l==r)return id[l];
	if(t[rt].v<k)return -1;
	int mid=l+r>>1,sum=t[lc(rt)].v;
	if(sum>=k)return Query(lc(rt),l,mid,k);
	else return Query(rc(rt),mid+1,r,k-sum);
}
int x,y;
int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	N=qr();M=qr();
	for(int i=1;i<=N;i++)a[i]=qr(),f[i]=id[a[i]]=i;
	for(int i=1;i<=M;i++){
		x=findf(qr());y=findf(qr());
		if(x!=y)f[x]=y;
	}
	for(int i=1;i<=N;i++)Insert(a[i],1,N,root[findf(i)]);
	Q=qr();char op;
	for(int i=1;i<=Q;i++){
		op=getchar();while(op<'A'||op>'Z')op=getchar();
		x=qr();y=qr();
		if(op=='B'){
			x=findf(x);y=findf(y);
			if(x!=y)f[x]=y,root[y]=Merge(root[x],root[y]);
		}
		else printf("%d\n",Query(root[findf(x)],1,N,y));
	}
	return 0;
}