3324 永无乡

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n, m, q, f[N];
int root[N], tot;
int ls[N*20], rs[N*20], id[N*20], sum[N*20];
// id:节点编号， sum：重要度的出现次数之和 
// 时间空间复杂度为nlogn 
int find(int x){
	if(x == f[x])
		return x;
	return f[x] = find(f[x]);
}

void pushup(int p){
	sum[p] = sum[ls[p]] + sum[rs[p]];
}

int update(int u, int pl, int pr, int p, int i){
	if(!u) u = ++tot;
	//sum[u] ++; //如果sum[u]++写在这里，就可以不需要pushup操作。 
	if(pl == pr){
		id[u] = i;
		sum[u] ++;
		return u;
	}
	int mid = (pl + pr) / 2;
	if(p <= mid)
		ls[u] = update(ls[u], pl, mid, p, i);
	else
		rs[u] = update(rs[u], mid+1, pr, p, i);
	pushup(u);
	return u; 
}

int merge(int x, int y, int pl, int pr){
	if(!x || !y) return x + y;
	if(pl == pr){
		sum[x] += sum[y];
		return x;
	}
	int mid = (pl + pr) / 2;
	ls[x] = merge(ls[x], ls[y], pl, mid);
	rs[x] = merge(rs[x], rs[y], mid + 1, pr);
	pushup(x);
	return x;
}
int query(int u, int pl, int pr, int k){
	if(pl == pr) return id[u];
	int ans = 0;
	int mid = (pl + pr) / 2;
	if(k <= sum[ls[u]]) ans = query(ls[u], pl, mid, k);
	else ans = query(rs[u], mid+1, pr, k-sum[ls[u]]);
	return ans;
}

int main(){
	int x, y;
	scanf("%d%d",&n, &m);
	for(int i=1; i<=n; i++){
		f[i] = i;
		scanf("%d",&x);
		root[i] = update(root[i], 1, n, x, i); 
	}
	for(int i=1; i<=m; i++){
		scanf("%d%d",&x, &y);
		x = find(x);
		y = find(y);
		if(x == y) continue; 
		f[y] = x;
		root[x] = merge(root[x], root[y], 1, n);
	}
	scanf("%d",&q);
	while(q--){
		char ch[5];
		scanf("%s", ch);
		if(ch[0] == 'B'){
			scanf("%d%d",&x, &y);
			x = find(x);
			y = find(y);
			if(x == y) continue;
			f[y] = x;
			root[x] = merge(root[x], root[y], 1, n); 
		}
		else{
			scanf("%d%d",&x, &y);
			x = find(x);
			int ans = query(root[x], 1, n, y);
			ans = ans? ans:-1;
			printf("%d\n", ans); 
		}
	}
	return 0;
}