永无乡问题

解题思路

本题有 $n$ 个小岛，每个小岛都有一个重要度，然后岛与岛之间会有桥，我们每次可以加上一个桥，也可以查询与某个岛连通的所有岛中重要度第 $k$ 小的岛的编号是几。

首先发现本题存在一个连通性需要我们维护，我们可以用并查集来维护，如果两个岛连通，则认为他们在同一个集合中。

这样每加一条边就等于是将两个集合合并，对于并查集来说比较好处理，剩下的问题是如何来查询。

我们其实就是要查询某一个集合中第 $k$ 小的数，还要支持一个合并的操作，因此就是动态查询第 $k$ 小的数，这是可以用平衡树 Splay 来维护的。

但是在查询的过程中，我们还要支持动态的合并两个集合，而 Splay 是不支持合并的，这里需要采用一个技巧，叫做启发式合并，就是如果我们现在有 $n$ 个元素，我们最终要将这 $n$ 个元素合并成 $1$ 个元素，那么我们可以用在每次合并时，都将元素数量较小的集合合并到元素数量较大的集合中去，这样就能保证最终合并的时间复杂度是 $O(NlogN)$ 的，这就是启发式合并。

因此对于每一个集合，我们都用一个 Splay 去维护，当要将两个集合合并时，我们看一下哪个集合比较大，将较小的集合合并到较大集合中就可以了，因为两个 Splay 本身是没法合并的，因此我们这里就是将较小的集合中的元素一个一个插入到较大的集合对应的 Splay 中，由于这是启发式合并，所以合并的时间复杂度是 $O(NlogN)$，而每插入一个元素需要 $O(logN)$ 的时间复杂度，因此整个算法的时间复杂度应该是 $O(Nlog^2N)$

注意，之所以这里不能将 Splay 合并是因为我们要求第 $k$ 小数，所以每个 Splay 内部的元素都是有序的，而如果我们要将两个 Splay 合并，我们是很难在较短的时间复杂度内将两个 Splay 合并的同时还要保证合并后的 Splay 内部的元素有序，而如果不保证 Splay 内部的有序性，其实是可以进行合并的。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 500010, M = 100010;

int n, m, q;

struct Node
{
    int s[2], p, v, id; //两个子节点的下标、父节点的下标、重要度、编号
    int cnt; //当前节点为根的子树中的节点数量

    void init(int _v, int _id, int _p) //初始化每个节点
    {
        v = _v, id = _id, p = _p;
        cnt = 1;
    }
}tr[N]; //Splay

int root[M], idx; //记录每个 Splay 的根节点下标
int p[M]; //并查集

int find(int x) //找到 x 所在集合的根节点
{
    if(x != p[x]) p[x] = find(p[x]);
    return p[x];
}

void pushup(int x) //通过子节点的信息得到当前节点的信息
{
    tr[x].cnt = tr[tr[x].s[0]].cnt + tr[tr[x].s[1]].cnt + 1;
}

void rotate(int x) //左旋、右旋
{
    int y = tr[x].p, z = tr[y].p;
    int k = tr[y].s[1] == x;
    tr[z].s[tr[z].s[1] == y] = x, tr[x].p = z;
    tr[y].s[k] = tr[x].s[k ^ 1], tr[tr[x].s[k ^ 1]].p = y;
    tr[x].s[k ^ 1] = y, tr[y].p = x;
    pushup(y), pushup(x);
}

void splay(int x, int k, int b) //将集合 b 的 Splay 中的 x 节点转到 k 节点的下面
{
    while(tr[x].p != k)
    {
        int y = tr[x].p, z = tr[y].p;
        if(z != k)
        {
            if((tr[y].s[1] == x) ^ (tr[z].s[1] == y)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    if(!k) root[b] = x;
}

void insert(int v, int id, int b) //将编号为 id，重要度为 v 的节点加入集合 b 的 Splay 中
{
    int u = root[b], p = 0;
    while(u) p = u, u = tr[u].s[v > tr[u].v];
    u = ++idx;
    if(p) tr[p].s[v > tr[p].v] = u;
    tr[u].init(v, id, p);
    splay(u, 0, b);
}

int get_k(int k, int b) //查询集合 b 的 Splay 中重要度第 k 小的节点编号
{
    int u = root[b];
    while(u)
    {
        if(tr[tr[u].s[0]].cnt >= k) u = tr[u].s[0];
        else if(tr[tr[u].s[0]].cnt + 1 == k) return tr[u].id;
        else k -= tr[tr[u].s[0]].cnt + 1, u = tr[u].s[1];
    }
    return -1;
}

void dfs(int u, int b) //将根节点 u 所在 Splay 中的每一个点插入到集合 b 的 Splay 中
{
    if(tr[u].s[0]) dfs(tr[u].s[0], b); //递归插入左子节点
    if(tr[u].s[1]) dfs(tr[u].s[1], b); //递归插入右子节点
    insert(tr[u].v, tr[u].id, b); //将 u 节点插入集合 b 的 Splay 中
}

int main()
{
    scanf("%d%d", &n, &m);

    //初始化
    for(int i = 1; i <= n; i++)
    {
        p[i] = i; //初始化并查集
        root[i] = i; //记录第 i 个节点为根节点的集合所在的 Splay 的根节点下标
        int v;
        scanf("%d", &v);
        tr[i].init(v, i, 0); //初始化每个集合的根节点
    }
    idx = n; //前 n 个下标给 n 个 Splay 的根节点用

    while(m--)
    {
        int a, b;
        scanf("%d%d", &a, &b);

        a = find(a), b = find(b);
        if(a != b) //如果两个岛不在一个集合里，需要合并
        {
            if(tr[root[a]].cnt > tr[root[b]].cnt) swap(a, b); //保证集合 a 中元素个数 <= 集合 b 中元素个数
            dfs(root[a], b); //将集合 a 的 Splay 里的每一个点插入到集合 b 的 Splay 里面
            p[a] = b; //将集合 a 合并入集合 b
        }
    }

    scanf("%d", &q);
    while(q--)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if(*op == 'B') //加边
        {
            a = find(a), b = find(b);
            if(a != b) //合并，同上
            {
                if(tr[root[a]].cnt > tr[root[b]].cnt) swap(a, b);
                dfs(root[a], b);
                p[a] = b;
            }
        }
        else //询问第 k 小数
        {
            a = find(a);
            if(tr[root[a]].cnt < b) puts("-1"); //集合中不足 b 个数，输出 -1
            else printf("%d\n", get_k(b, a)); //否则查询第 k 小数
        }
    }
    return 0;
}