记录编号	602002	评测结果	AAAAAAAAAA
题目名称	1341.[HNOI 2012] 永无乡	最终得分	100
用户昵称	李奇文	是否通过	通过
代码语言	C++	运行时间	2.832 s
提交时间	2025-06-30 10:54:41	内存使用	32.83 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int cnt,n,m,q,fa[N],f[N],ans[N];
struct node{
	int l,r,sum,son[2];
}t[N*40];
int find(int x){
	return (x==fa[x])?x:fa[x]=find(fa[x]);
}
int insert(int p,int l,int r){
	int pp=++cnt;
	t[pp].l=l,t[pp].r=r,t[pp].sum=1;
	if(l==r) return pp;
	int mid=(l+r)>>1;
	if(p>mid) t[pp].son[1]=insert(p,mid+1,r);
	else t[pp].son[0]=insert(p,l,mid);
	return pp;
}
int hebin(int x,int y,int l,int r){
	if(!x&&!y) return 0;
	if(!x) return y;
	if(!y) return x;
	int pp=++cnt;
	int mid=(l+r)>>1;
	t[pp].l=l,t[pp].r=r,t[pp].sum=t[x].sum+t[y].sum;
	t[pp].son[0]=hebin(t[x].son[0],t[y].son[0],l,mid);
	t[pp].son[1]=hebin(t[x].son[1],t[y].son[1],mid+1,r);
	return pp;
}
int query(int x,int k){
	if(t[x].sum<k) return -1;
	if(t[x].l==t[x].r) return ans[t[x].l];
	if(t[t[x].son[0]].sum>=k) return query(t[x].son[0],k);
	else return query(t[x].son[1],k-t[t[x].son[0]].sum);
}
int main(){
	freopen("bzoj_2733.in","r",stdin);
	freopen("bzoj_2733.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(register int i=1,x;i<=n;++i){
		scanf("%d",&x);
		fa[i]=i,ans[x]=i;
		f[i]=insert(x,1,n);
	}
	for(register int i=1,x,y;i<=m;++i){
		scanf("%d%d",&x,&y);
		int a=find(x),b=find(y);
		if(a==b) continue;
		fa[a]=b,f[b]=hebin(f[a],f[b],1,n);
	} 
	cin>>q;
	while(q--){
		char c;
		int x,y;
		cin>>c;
		scanf("%d%d",&x,&y);
		if(c=='Q'){
			printf("%d\n",query(f[find(x)],y));
		}else{
			int a=find(x),b=find(y);
			if(a==b) continue;
			fa[a]=b;
			f[b]=hebin(f[a],f[b],1,n);
		}
	}
	return 0;
}