题目描述
永无乡包含 nn 座岛，编号从 11 到 nn ，每座岛都有自己的独一无二的重要度，按照重要度可以将这 nn 座岛排名，名次用 11 到 nn 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 aa 出发经过若干座（含 00 座）桥可以 到达岛 bb ，则称岛 aa 和岛 bb 是连通的。

现在有两种操作：

B x y 表示在岛 xx 与岛 yy 之间修建一座新桥。

Q x k 表示询问当前与岛 xx 连通的所有岛中第 kk 重要的是哪座岛，即所有与岛 xx 连通的岛中重要度排名第 kk 小的岛是哪座，请你输出那个岛的编号。

后面剩下的部分描述操作，该部分的第一行是一个正整数 qq ，表示一共有 qq 个操作，接下来的 qq 行依次描述每个操作，操作的 格式如上所述，以大写字母 QQ 或 BB 开始，后面跟两个不超过 nn 的正整数，字母与数字以及两个数字之间用空格隔开。

输出格式
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出 -1−1 。

输入输出样例
输入 #1复制
5 1
4 3 2 5 1
1 2
7
Q 3 2
Q 2 1
B 2 3
B 1 5
Q 2 1
Q 2 4
Q 2 3

输出 #1复制
-1
2
5
1
2

说明/提示
对于 20% 的数据 n \leq 1000, q \leq 1000n≤1000,q≤1000

对于 100% 的数据 n \leq 100000, m \leq n, q \leq 300000n≤100000,m≤n,q≤300000

第一点，会用到并查集，肯定很明显。

然后我们需要记录权值以及找第K小的问题，所以我们可以用平衡树来合并，或者权值线段树合并。

然后直接输出即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10,M=N*20;
int n,m,q,val[N],vis[N],f[N];
int rt[N],sum[M],lc[M],rc[M],cnt;
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
void change(int &p,int l,int r,int x){
	if(!p)	p=++cnt;
	if(l==r){sum[p]++; return ;}
	int mid=l+r>>1;
	if(x<=mid)	change(lc[p],l,mid,x);
	else	change(rc[p],mid+1,r,x);
	sum[p]=sum[lc[p]]+sum[rc[p]];
}
int ask(int p,int l,int r,int k){
	if(!p)	return 0;
	if(l==r)	return l; int mid=l+r>>1;
	if(sum[lc[p]]>=k)	return ask(lc[p],l,mid,k);
	else	return ask(rc[p],mid+1,r,k-sum[lc[p]]);
}
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]);
	sum[x]=sum[lc[x]]+sum[rc[x]];
	return x;
}
signed main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)	f[i]=i; vis[0]=-1;
	for(int i=1;i<=n;i++)	
		scanf("%d",&val[i]),vis[val[i]]=i,change(rt[i],1,n,val[i]);
	for(int i=1,x,y;i<=m;i++){
		scanf("%d %d",&x,&y);	x=find(x),y=find(y);
		f[y]=x;	merge(rt[x],rt[y]);	
	}
	cin>>q;
	while(q--){
		char op[2]; int x,y; scanf("%s %d %d",op,&x,&y);
		if(op[0]=='Q'){
			x=find(x);	printf("%d\n",vis[ask(rt[x],1,n,y)]);
		}else{
			x=find(x),y=find(y); f[y]=x; merge(rt[x],rt[y]);
		}
	}
	return 0;
}