洛谷P3224 [HNOI2012]永无乡 题解 splay tree 启发式合并

题目链接：https://www.luogu.com.cn/problem/P3224

主要知识点是：树上启发式合并，即每次合并将小的树里面的每个点合并大大的树里面，时间复杂度 \(O(n \log^2 n)\)。

同时需要开并查集维护集合关系。

示例程序：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 5;

struct Node {
    int s[2], p, v, id, sz;
    Node() {}
    Node(int _v, int _id, int _p) {
        v = _v; id = _id; p = _p;
        sz = 1;
        s[0] = s[1] = 0;
    }
} tr[maxn];
int root[maxn], idx;
int p[maxn];

int find(int x) {
    return x == p[x] ? x : p[x] = find(p[x]);
}

void push_up(int x) {
    tr[x].sz = tr[tr[x].s[0]].sz + tr[tr[x].s[1]].sz + 1;
}

void f_s(int p, int u, bool k) {
    tr[p].s[k] = u;
    tr[u].p = p;
}

void rot(int x) {
    int y = tr[x].p, z = tr[y].p;
    bool k = tr[y].s[1] == x;
    f_s(z, x, tr[z].s[1]==y);
    f_s(y, tr[x].s[k^1], k);
    f_s(x, y, k^1);
    push_up(y), push_up(x);
}

void splay(int x, int k, int b) {
    while (tr[x].p != k) {
        int y = tr[x].p, z = tr[y].p;
        if (z != k)
            (tr[y].s[1]==x) ^ (tr[z].s[1]==y) ? rot(x) : rot(y);
        rot(x);
    }
    if (!k) root[b] = x;
}

void ins(int v, int id, int b) {
    int u = root[b], p = 0;
    while (u) p = u, u = tr[u].s[v > tr[u].v];
    tr[u = ++idx] = Node(v, id, p);
    if (p) tr[p].s[v > tr[p].v] = u;
    splay(u, 0, b);
}

int get_k(int k, int b) {
    int u = root[b];
    while (u) {
        if (tr[tr[u].s[0]].sz >= k) u = tr[u].s[0];
        else if (tr[tr[u].s[0]].sz + 1 == k) return tr[u].id;
        else k -= tr[tr[u].s[0]].sz + 1, u = tr[u].s[1];
    }
    return -1;
}

void dfs(int u, int b) {
    if (tr[u].s[0]) dfs(tr[u].s[0], b);
    if (tr[u].s[1]) dfs(tr[u].s[1], b);
    ins(tr[u].v, tr[u].id, b);
}

int n, m;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        p[i] = root[i] = i;
        int v;
        scanf("%d", &v);
        tr[i] = Node(v, i, 0);
    }
    idx = n;
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        a = find(a), b = find(b);
        if (a != b) {
            if (tr[root[a]].sz > tr[root[b]].sz) swap(a, b);
            dfs(root[a], b);
            p[a] = b;
        }
    }
    scanf("%d", &m);
    while (m--) {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        if (op[0] == 'B') {
            a = find(a), b = find(b);
            if (a != b) {
                if (tr[root[a]].sz > tr[root[b]].sz) swap(a, b);
                dfs(root[a], b);
                p[a] = b;
            }
        }
        else {
            a = find(a);
            if (tr[root[a]].sz < b) puts("-1");
            else printf("%d\n", get_k(b, a));
        }
    }
    return 0;
}