「BZOJ 3376」Cube Stacking - 带权并查集

发表于 | 分类于

约翰和贝茜在玩一个方块游戏。编号为 到 的 个方块正放在地上．每个构成一个立方柱。

游戏开始后，约翰会给贝茜发出 个指令。指令有两种：

  1. 移动：将包含 的立方柱移动到包含 的立方柱上；
  2. 统计：统计名含 的立方柱中，在 下方的方块数目。

写个程序帮贝茜完成游戏。

链接

BZOJ 3376

题解

带权并查集，以每堆方块最下面的方块为并查集的树根，记录每堆方块最上面的方块编号，每次合并将 块的根的父节点置为 所在堆最上面的方块。记 为从 （包含）到 的父节点（不包含）之间的方块数量。每次查询将 取一个前缀和即可。

注意路径压缩时的处理。

代码

#include <cstdio>

const int MAXN = 300000;

struct UFS {
    int f[MAXN + 1], d[MAXN + 1], h[MAXN + 1];

    void init(int n) {
        for (int i = 1; i <= n; i++) f[i] = i, h[i] = i;
    }

    int find(int x) {
        if (f[x] == x) {
            return x;
        }
        int y = find(f[x]);
        // printf("d[%d] = %d\n", x, d[x]);
        d[x] += d[f[x]];
        f[x] = y;
        // h[x] = h[y];
        return y;
    }

    void merge(int fa, int ch) {
        // printf("merge %d to %d\n", ch, fa);
        h[find(fa)] = h[find(ch)];
        f[ch] = fa;
        d[ch] = 1;
    }
} ufs;

int main() {
    ufs.init(MAXN);

    int m;
    scanf("%d", &m);
    while (m--) {
        char s[2];
        scanf("%s", s);
        if (*s == 'M') {
            int x, y;
            scanf("%d %d", &x, &y);
            ufs.merge(ufs.h[ufs.find(y)], ufs.find(x));
        } else {
            int x;
            scanf("%d", &x);
            ufs.find(x);
            printf("%d\n", ufs.d[x]);
        }
    }

    return 0;
}