「Bzoj 2733」「HNOI2012」永无乡 (权值线段树 / Splay森林 + 启发式合并)

发表于 | | + s

Bzoj 2733
题意：维护一个无向图，有两种操作：

  • B x y 表示在岛 $x$ 与岛 $y$ 之间修建一座新桥。
  • Q x k 表示询问当前与岛 $x$ 连通的所有岛中第 $k$ 重要的是哪座岛，即所有与岛 $x$ 连通的岛中重要度排名第 $k$ 小的岛是哪座，请你输出那个岛的编号。

这题一开始看见连边以为是$LCT$，但是这题不断边，所以直接并查集维护即可。对于每个联通块开一个 Splay 处理第 $k$ 大即可，这里值域小也可以开权值线段树，更加方便。

合并则使用启发式合并，复杂度为$O(n\log n)$，注意代码实现细节

知识点
1、Splay有时候值域小也可以开权值线段树，更加方便

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    int n, m, q, f_dsu[MAXN];
    int ch[MAXN][2], fa[MAXN], val[MAXN], siz[MAXN], sz, rt[MAXN];

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

    int rel(int x) {return ch[fa[x]][1] == x;}
    void pushup(int x) {siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;}
    void rotate(int x) {
        int y = fa[x], z = fa[y], k = rel(x), w = ch[x][k ^ 1];
        ch[z][rel(y)] = x, fa[x] = z;
        ch[y][k] = w, fa[w] = y;
        ch[x][k ^ 1] = y, fa[y] = x;
        pushup(y), pushup(x);
    }
    void splay(int x, int gg) { // 在 gg 所在子 Splay 中将 x Splay 到根 
        while (fa[x] != 0) {
            int y = fa[x];
            if (fa[y] != 0) {
                if (rel(x) == rel(y)) rotate(y); else rotate(x);
            }
            rotate(x);
        }
        rt[gg] = x;
    }
    int newNode(int v) { // 新建一个节点 
        ++sz;
        ch[sz][0] = ch[sz][1] = fa[sz] = 0, val[sz] = v, siz[sz] = 1;
        return sz;
    }
    void insert(int x, int gg) { // 在 gg 所在子 Splay 中插入 x 节点 
        int v = val[x];
        int cur = rt[gg], p = 0;
        while (cur && v != val[cur]) p = cur, cur = ch[cur][v > val[cur]];
        cur = x;
        fa[cur] = p, ch[p][v > val[p]] = cur;
        splay(cur, gg);
    }
    int kth(int k, int gg) { // 在 gg 所在子 Splay 中找 k 大值 
        int cur = gg;
        while (1) {
            if (k <= siz[ch[cur][0]]) cur = ch[cur][0];
            else if (k > siz[ch[cur][0]] + 1) k -= siz[ch[cur][0]] + 1, cur = ch[cur][1];
            else return cur;
        }
    }
    void merge(int x, int &to) { // 合并两个 Splay x -> to
        if (ch[x][0]) merge(ch[x][0], to);
        if (ch[x][1]) merge(ch[x][1], to);
        ch[x][0] = ch[x][1] = 0, insert(x, to);
        pushup(x);
    }

    void clean() {
        sz = 0;
    }
    int solve() {

        clean();
        cin >> n >> m;
        for (int x, i = 1; i <= n; ++i) {
            scanf("%d", &x), f_dsu[i] = rt[i] = i;
            insert(newNode(x), i);
        }
        for (int x, y, i = 1; i <= m; ++i) {
            scanf("%d%d", &x, &y);
            int a = find(x), b = find(y);
            if (a != b) {
                if (siz[rt[a]] > siz[rt[b]]) swap(a, b);
                f_dsu[a] = b, merge(rt[a], b);
            }
        }
        cin >> q;
        while (q--) {
            char s[3];
            scanf("%s", s);
            if (s[0] == 'B') {
                int x, y;
                scanf("%d%d", &x, &y);
                int a = find(x), b = find(y);
                if (a != b) {
                    if (siz[rt[a]] > siz[rt[b]]) swap(a, b);
                    f_dsu[a] = b, merge(rt[a], b);
                }
            } else if (s[0] == 'Q') {
                int x, k;
                scanf("%d%d", &x, &k);
                int a = find(x);
                splay(rt[a], a);
                if (siz[rt[a]] < k) printf("-1\n"); else {
                    printf("%d\n", kth(k, rt[a]));
                }
            }

        }

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
5  1
4  3 2 5 1
1  2
1000
B 1 4
Q 1 3
*/
------ 本文结束 ------