[BZOJ2733][HNOI2012]永无乡（平衡树+启发式合并）

首先，构建出 n 棵平衡树，每棵平衡树只有一个节点，第 i 棵平衡树只包含第 i 座岛的相关信息。然后使用并查集维护岛之间的连通关系，对于加边操作，如果并查集中点 x 和 y 不连通，那么就在并查集中连接点 x 和 y ，并把 x 和 y 所在的平衡树合并。否则不做任何操作。
而对于合并两棵平衡树，可以使用启发式合并，即把点数较少的平衡树中的点暴力合并到点数较多的平衡树上。实际上，这样操作，每个点被合并的次数不超过 O(logn) 。
证明：由于启发式合并是把点数较少的平衡树合并到点数较多的平衡树上，所以一个点每被合并一次，所在的平衡树点数就至少扩大一倍，即被合并的次数不超过 O(logn) 。
对于询问操作，就是平衡树的「求排名为 k 的数」的问题，就不多说了。
代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
int res = 0; bool bo = 0; char c;
while (((c = getchar()) < '0' || c > '9') && c != '-');
if (c == '-') bo = 1; else res = c - 48;
while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
return bo ? ~res + 1 : res;
}
inline char get() {
char c; while ((c = getchar()) != 'B' && c != 'Q');
return c;
}
const int N = 1e5 + 5;
int n, m, q, f[N], fa[N], lc[N], rc[N], val[N], sze[N];
int cx(int x) {
if (f[x] != x) f[x] = cx(f[x]);
return f[x];
}
bool zm(int x, int y) {
int ix = cx(x), iy = cx(y);
if (ix != iy) {f[iy] = ix; return 1;}
return 0;
}
int which(int x) {return rc[fa[x]] == x;}
void upt(int x) {
    sze[x] = 1;
if (lc[x]) sze[x] += sze[lc[x]];
if (rc[x]) sze[x] += sze[rc[x]];
}
void rotate(int x) {
int y = fa[x], z = fa[y], b = lc[y] == x ? rc[x] : lc[x];
if (z) (lc[z] == y ? lc[z] : rc[z]) = x;
    fa[x] = z; fa[y] = x; if (b) fa[b] = y;
if (lc[y] == x) rc[x] = y, lc[y] = b;
else lc[x] = y, rc[y] = b; upt(y); upt(x);
}
void splay(int x) {
while (fa[x]) {
if (fa[fa[x]]) {
if (which(x) == which(fa[x])) rotate(fa[x]);
else rotate(x);
        }
        rotate(x);
    }
    upt(x);
}
void ins(int rt, int z) {
int x = rt, y;
while (x) {
        y = x; sze[x]++;
if (val[z] < val[x]) x = lc[x];
else x = rc[x];
    }
if (val[z] < val[y]) lc[fa[z] = y] = z;
else rc[fa[z] = y] = z;
}
void dfs(int y, int x) {
if (lc[x]) dfs(y, lc[x]);
if (rc[x]) dfs(y, rc[x]);
    fa[x] = lc[x] = rc[x] = 0;
    sze[x] = 1; ins(y, x);
}
void merg(int x, int y) {
if (!zm(x, y)) return;
    splay(x); splay(y);
if (sze[x] < sze[y]) swap(x, y);
    dfs(x, y);
}
int query(int x, int y) {
    splay(x);
while (x) {
int tmp = lc[x] ? sze[lc[x]] : 0;
if (y == tmp + 1) return x;
else if (y <= tmp) x = lc[x];
else x = rc[x], y -= tmp + 1;
    }
return -1;
}
int main() {
int i, x, y; n = read(); m = read(); char op;
for (i = 1; i <= n; i++) f[i] = i, sze[i] = 1, val[i] = read();
while (m--) x = read(), y = read(), merg(x, y); q = read();
while (q--) {
        op = get(); x = read(); y = read();
if (op == 'B') merg(x, y);
else printf("%d\n", query(x, y));
    }
return 0;
}