用的splay+启发式合并

#include <bits/stdc++.h>
using namespace std;
namespace ylz {
	const int N = 1e5 * 16 + 5;
	int n, m, Q;
	struct splay_tree {
		int son[2];
		int fa, sz, val;
	} t[N];
	int rt[N], tot;
	int f[N], box[N];
	int get(int x) {
		return t[t[x].fa].son[1] == x;
	}
	int find(int x) {
		return f[x] == x ? x : f[x] = find(f[x]);
	}
	void pushup(int p) {
		t[p].sz = t[t[p].son[0]].sz + t[t[p].son[1]].sz + 1;
	}
	void rotate(int x) {
		int y = t[x].fa, z = t[y].fa;
		int sonk = get(x);
		t[y].son[sonk] = t[x].son[sonk ^ 1];
		if (t[x].son[sonk ^ 1]) t[t[x].son[sonk ^ 1]].fa = y;
		t[x].son[sonk ^ 1] = y;
		t[y].fa = x;
		t[x].fa = z;
		if (z) t[z].son[y == t[z].son[1]] = x;
		pushup(x);
		pushup(y);
	}
	void splay(int x, int goal) {
		for (int f = t[x].fa; f = t[x].fa, f != goal; rotate(x))
			if (t[f].fa != goal) rotate(get(x) == get(f) ? f : x);
		if (goal <= n) rt[goal] = x;
	}
	void insert(int x, int k) {
		int p = rt[k], ff = k;
		while (p && t[p].val != x)
			ff = p, p = t[p].son[x > t[p].val];
		p = ++tot;
		t[p].sz = 1;
		t[p].fa = ff;
		if (ff > n)
			t[ff].son[x > t[ff].val] = p;
		t[p].val = x;
		t[p].son[0] = t[p].son[1] = 0;
		splay(p, k);
	}
	void Join(int x, int y) {
		if (t[x].son[0]) Join(t[x].son[0], y);
		if (t[x].son[1]) Join(t[x].son[1], y);
		insert(t[x].val, y);
	}
	void merge(int a, int b) {
		int x = find(a), y = find(b);
		if (x == y) return;
		if (t[rt[x]].sz > t[rt[y]].sz) swap(x, y);
		f[x] = y;
		Join(rt[x], y);
	}
	int kth(int p, int k) {
		int cur = rt[p];
		if (t[cur].sz < k) return -1;
		while (1) {
			if (t[t[cur].son[0]].sz + 1 < k) {
				k -= t[t[cur].son[0]].sz + 1;
				cur = t[cur].son[1];
			}
			else {
				if (t[t[cur].son[0]].sz >= k) {
					cur = t[cur].son[0];
				}
				else {
					return t[cur].val;
				}
			}
		}
	}
	int main() {
		scanf ("%d%d", &n, &m);
		for (int i = 1; i <= n; ++i) rt[i] = i + n, f[i] = i;
		tot = n + n;
		for (int i = 1, x; i <= n; ++i) {
			scanf ("%d", &x);
			box[x] = i;
			t[i + n].val = x;
			t[i + n].sz = 1;
			t[i + n].fa = i;
		}
		for (int i = 1, x, y; i <= m; ++i) {
			scanf ("%d%d", &x, &y);
			merge(x, y);
		}
		scanf ("%d", &Q);
		while (Q--) {
			int a, b;
			char op[3];
			scanf ("%s%d%d", op, &a, &b);
			if (op[0] == 'B') {
				merge(a, b);
			} else {
				int ans = kth(find(a), b);
				printf ("%d\n", ans == -1 ? ans : box[ans]);
			}
		}
		return 0;
	}
}
int main() {
	return ylz :: main();
}