记录编号	593626	评测结果	AAAAAAAAAA
题目名称	[HNOI 2012] 永无乡	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	2.787 s
提交时间	2024-09-06 01:45:12	内存使用	13.51 MiB

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
	int x=0,f=1,ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch&15);
	return f*x;
}
char c;
int n,m,p[100005],f[100005],mnp[100005],u,v,q,tot,tr[100005],ls[5000005],rs[5000005],sum[5000005];
int find(int x){
	return f[x]^x?f[x]=find(f[x]):x;
}
void Add(int &p,int l,int r,int x){
	if(!p) p=++tot;
	sum[p]++;
	if(l==r) return ;
	int mid=l+r>>1;
	if(x<=mid) Add(ls[p],l,mid,x);
	else Add(rs[p],mid+1,r,x);
}
int merge(int a,int b,int l,int r){
	if(!a||!b) return a|b;
	if(l==r){
		sum[a]+=sum[b];
		return a;
	}
	int mid=l+r>>1;
	ls[a]=merge(ls[a],ls[b],l,mid);
	rs[a]=merge(rs[a],rs[b],mid+1,r);
	sum[a]=sum[ls[a]]+sum[rs[a]];
	return a;
}
int query(int p,int l,int r,int x){
	if(l==r) return sum[p]==x?l:n+1;
	int mid=l+r>>1;
	return sum[ls[p]]>=x?query(ls[p],l,mid,x):query(rs[p],mid+1,r,x-sum[ls[p]]);
}
int main(){
	freopen("bzoj_2733.in","r",stdin);
    freopen("bzoj_2733.out","w",stdout);
	n=read(),m=read(),mnp[n+1]=-1;
	for(int i=1;i<=n;i++) p[i]=read(),f[i]=i,Add(tr[i],1,n,p[i]),mnp[p[i]]=i;
	while(m--){
		u=read(),v=read(),u=find(u),v=find(v);
		if(u^v) tr[u]=merge(tr[u],tr[v],1,n),f[v]=u;
	}
	q=read();
	while(q--){
		cin>>c,u=read(),v=read();
		if(c=='B'){
			u=find(u),v=find(v);
			if(u^v) tr[u]=merge(tr[u],tr[v],1,n),f[v]=u;
		}
		else printf("%d\n",mnp[query(tr[find(u)],1,n,v)]);
	}
	return 0;
}