题目地址：洛谷：【P3224】[HNOI2012]永无乡 – 洛谷、BZOJ：Problem 2733. — [HNOI2012]永无乡

题目描述

永无乡包含 n 座岛，编号从 1 到 n，每座岛都有自己的独一无二的重要度，按照重要度可以将这 n 座岛排名，名次用 1 到 n 来表示。某些岛之间由巨大的桥连接，通过桥可以从一个岛到达另一个岛。如果从岛 a 出发经过若干座（含 0 座）桥可以到达岛 b，则称岛 a 和岛 b 是连通的。
现在有两种操作：
B x y 表示在岛 x 与岛 y 之间修建一座新桥。
Q x k 表示询问当前与岛 x 连通的所有岛中第 k 重要的是哪座岛，即所有与岛 x 连通的岛中重要度排名第 k 小的岛是哪座，请你输出那个岛的编号。

题意简述

给你一个$n$个点有点权的图，两种操作：

1. 加边
2. 询问连通块$k$小点

输入输出格式

输入格式：
输入文件第一行是用空格隔开的两个正整数 n 和 m，分别表示岛的个数以及一开始存在的桥数。
接下来的一行是用空格隔开的 n 个数，依次描述从岛 1 到岛 n 的重要度排名。
随后的 m 行每行是用空格隔开的两个正整数 ai 和 bi，表示一开始就存在一座连接岛 ai 和岛 bi 的桥。
后面剩下的部分描述操作，该部分的第一行是一个正整数 q，表示一共有 q 个操作，接下来的 q 行依次描述每个操作，操作的格式如上所述，以大写字母 Q 或 B 开始，后面跟两个不超过 n 的正整数，字母与数字以及两个数字之间用空格隔开。

输出格式：
对于每个 Q x k 操作都要依次输出一行，其中包含一个整数，表示所询问岛屿的编号。如果该岛屿不存在，则输出-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≤1000, q≤1000
对于 100% 的数据 n≤100000, m≤n, q≤300000

题解

其实把图上的连通块看成集合就是个裸题了。我们考虑使用Splay维护集合，加边等价于合并两个集合，启发式合并即可，询问$k$小直接做就好。注意已经是一个集合内的情况不需要加边，而且加边存在数据不合法（即$a_i, b_i < 1$或$a_i, b_i > n$的情况），需要把这些边忽略。
复杂度$O(n \log n)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = res * 10 + c - '0';
    return res * neg;
}

inline char readsingle() {
    register char c;
    while(!isgraph(c = fgc())) {}
    return c;
}

const int MAXN = 100005;

int n, m, q;

struct Node {
    int ch[2], fa, val, siz;
} tr[MAXN];
int tot;

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline void update(int p) {
    if(!p) return;
    tr[p].siz = tr[tr[p].ch[0]].siz + tr[tr[p].ch[1]].siz + 1;
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(ffa) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    for(int fa = tr[p].fa; fa; rotate(p), fa = tr[p].fa) {
        if(tr[fa].fa) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline int insert(int rt, int q) {
    int p = rt;
    for(;;) {
        bool t = tr[q].val > tr[p].val;
        if(!tr[p].ch[t]) {
            tr[p].ch[t] = q; tr[q].fa = p; tr[q].ch[0] = 0; tr[q].ch[1] = 0;
            splay(q); return q;
        }
        p = tr[p].ch[t];
    }
}

inline int queryk(int rt, int k) {
    int p = rt;
    for(;;) {
        if(k <= tr[tr[p].ch[0]].siz) {
            p = tr[p].ch[0];
        } else if(k == tr[tr[p].ch[0]].siz + 1) {
            splay(p); return p;
        } else {
            k -= tr[tr[p].ch[0]].siz + 1;
            p = tr[p].ch[1];
        }
    }
}

int sta[MAXN], stop;

void dfs(int p) {
    sta[stop++] = p;
    if(tr[p].ch[0]) dfs(tr[p].ch[0]);
    if(tr[p].ch[1]) dfs(tr[p].ch[1]);
}

inline void merge(int x, int y) {
    splay(x); splay(y);
    if(tr[x].fa || tr[y].fa || x == y) return;
    if(tr[x].siz > tr[y].siz) std::swap(x, y);
    stop = 0; dfs(x);
    for(int i = 0; i < stop; i++) {
        splay(y); insert(y, sta[i]);
    }
}

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        tr[i].val = readint();
        tr[i].siz = 1;
    }
    for(int i = 1, a, b; i <= m; i++) {
        a = readint(); b = readint();
        if(a < 1 || a > n || b < 1 || b > n) continue;
        merge(a, b);
    }
    q = readint();
    while(q--) {
        char op = readsingle();
        int a = readint(), b = readint();
        if(op == 'B') {
            merge(a, b);
        } else {
            splay(a);
            if(b > tr[a].siz) puts("-1");
            else printf("%d\n", queryk(a, b));
        }
    }
    return 0;
}