[HNOI2012]永无乡

线段树合并练手题，写这篇博客只是为了给我的找个板子题。

并查集维护连通性，对于不在同一个连通块内的合并操作每次直接合并两颗线段树，复杂度\(O(n \log n)\)。

//written by newbiechd#include 
    
     #define R register#define I inlineusing namespace std;const int N = 100003;int f[N], id[N], rt[N], T;struct segtree {    int p, q, s;}e[N << 5];I int find(int x) {    R int r = x, y;    while (f[r] ^ r)        r = f[r];    while (x ^ r)        y = f[x], f[x] = r, x = y;    return r;}void insert(int &k, int l, int r, int x) {    k = ++T, ++e[k].s;    if (l == r)        return ;    R int m = (l + r) >> 1;    if (x <= m)        insert(e[k].p, l, m, x);    else        insert(e[k].q, m + 1, r, x);}int merge(int k, int t, int l, int r) {    if (!k)        return t;    if (!t)        return k;    e[k].s += e[t].s;    if (l == r)        return k;    R int m = (l + r) >> 1;    e[k].p = merge(e[k].p, e[t].p, l, m),        e[k].q = merge(e[k].q, e[t].q, m + 1, r);    return k;}int query(int k, int l, int r, int x) {    if (l == r)        return l;    R int m = (l + r) >> 1, t = e[e[k].p].s;    if (x <= t)        return query(e[k].p, l, m, x);    else        return query(e[k].q, m + 1, r, x - t);}int main() {    R int n, m, Q, i, x, y, z;    R char opt[2];    scanf("%d%d", &n, &m);    for (i = 1; i <= n; ++i)        f[i] = i, scanf("%d", &z), id[z] = i, insert(rt[i], 1, n, z);    for (i = 1; i <= m; ++i)        scanf("%d%d", &x, &y), x = find(x), y = find(y), f[y] = x,            rt[x] = merge(rt[x], rt[y], 1, n);    scanf("%d", &Q);    for (i = 1; i <= Q; ++i) {        scanf("%s%d%d", opt, &x, &y), x = find(x);        if (opt[0] == 'B') {            y = find(y);            if (y ^ x)                f[y] = x, merge(rt[x], rt[y], 1, n);        }        else            if (y > e[rt[x]].s)                printf("-1\n");            else                printf("%d\n", id[query(rt[x], 1, n, y)]);    }    return 0;}