可持久化并查集学习笔记

前置技能

主席树及其常用操作（动态开点，可持久化）、并查集及其常用操作（启发式合并）

并查集中有几种合并方式：

一种是直接暴力连父亲（这显然很劣）
一种是路径压缩的合并（这个在普通并查集中很常用，但是好像无法在可持久化并查集中用，听说是可以构造数据使可持久化并查集的空间爆掉？）
还有一种是按秩（深度或子集大小）合并，也就是可持久化并查集中常用的合并方式！其实也就是一种类似于启发式合并的方式，每一次合并时选择一个小的集合向大的集合合并。这样就可以保证并查集的高度不会增长的太快，保证高度尽量均衡，从而避免退化。

步入正题 —— 可持久化并查集

可持久化并查集 - 例题传送门

其实我们可以发现看懂了前置技能后，可持久化并查集已经不难实现。

可持久化并查集其实就是指的用可持久化数组维护并查集中的 FaFa 与按秩合并所需要的 depdep

所谓可持久化并查集，可以进行的操作就只有几个：

回到历史版本（也就是可持久化）
合并两个集合
查询节点所在集合的祖先
判断是否在同一个集合中（也就是并查集）

对于 1 操作，我们可以很轻松的利用可持久化数组（或主席树）实现

对于 3&4 操作，也就是在可持久化数组中查询

而，对于 2 操作：

我们知道，平常时候使用的并查集优化是路径压缩，查询复杂度是均摊 $l o g$ 的。

但是均摊并不可以，因为我们无法保证某次查询复杂度不为 $O (n)$ ，如果这样对于可持久化来说是毁灭性的，如果你操作一次 $O (n)$ ，那么我们可能会被要求返回这个版本，再次进行这种~~不讲武德~~的操作。

所以我们要寻找一种 $f i n d$ 方式，使得我们的复杂度为严格 $l o g$ 的。

这时候，按秩合并就出现了，他就有 $l o g$ 的优美复杂度，还是严格的。

具体的，按秩合并又有多重方式，

按照深度
按照大小
随机

好的我们考虑前两个~~因为第 3 个能被卡掉~~

这里只讲深度，因为比较好理解，一次查询的复杂度应该为 $u \to r o o t$ 的距离，虽然这是棵树，但是不能保证~~邪恶的~~出题人不会给我们一条链子。

按照深度：我们不但记录某个点的 $f a$ 还需要记录这个点的子树的深度 $d e p$ 。

对于一次操作合并 $u, v$ 。

我们让 $u = f i n d (u), v = f i n d (v)$ 。

考虑把两者合并起来（假定 $d e p_{u} \geq d e p_{v}$ ）

我们显然应该把 $v$ 的子树合并到 $u$ 的下面。

只有这样才能保证深度尽可能的小。

我们考虑 $d e p u$ 变成了什么？

如果 $d e p_{u} = d e p_{v}$ ，那么我们把 $v$ 放到 $u$ 的下方， $d e p_{v}$ 增大了 1。由于 $d e p_{u}$ 表示的是以 $u$ 为根节点的深度所以 $d e p_{u} = d e p_{v} + 1$
如果 $d e p_{u} > d e p_{v}$ 深度不变。

如果按这样合并的顺序的话，全部合并完，我们的树高最大也只有 $l o g$ 。

所以复杂度为严格 $l o g$ 。

那么具体的，对于一次修改，我们需要新建 2 个版本。

首先将这个版本中的 $f a_{v}$ 变为 $u$ ，接着，我们需要修改 $d e p_{u}$ 。

如果你不是很懂为什么需要建立两个版本可以看这里：

首先我们需要明确新建的两个版本是什么：

将 $f a_{v}$ 变成 $u$ 这一步很好理解，没有什么问题。
将 $d e p_{u}$ 更新，这里很重要，一定要新建一个版本来更新 $d e p_{u}$ 否则会 TLE。

如果你不新建版本而是直接修改 $d e p_{u}$ ，那么假如当前版本是 $n o w$ ，我们知道 $n o w$ 这个版本是 $n o w - 1$ 版本修改 $f a_{v}$ （即 1. ）产生的，因此 $n o w$ 和 $n o w - 1$ 所对应的 $d e p_{u}$ 实际上是同一个数组。

如果你在 $n o w$ 版本直接修改了 $d e p_{u}$ 那么意味着 $n o w - 1$ 版本的 $d e p_{u}$ 同时被修改了，那么这时候，我们的 $d e p$ 数组就有可能不满足按秩合并的优美性质了，此时如果数据让我们回溯到 $n o w - 1$ 版本修改，那么可能就会导致按秩合并出错，从而产生 TLE。

NOTE

以上是使用主席树的实现方式，除此之外，还可以简单地使用两个可持久化数组来实现

AC 代码：

cpp

//	可持久化并查集 初学练习题 模板
//	https://www.luogu.com.cn/problem/P3402

#include <algorithm>
#include <cmath>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>

using namespace std;

mt19937_64 rnd(time(0));

typedef long long ll;
typedef uint64_t ull;

const ll INF = 1e18, Mod = 1e9 + 7;

ll n, m;
ll root[200010];

struct Node {
    ll lson, rson, val;
};

struct Array {
    Node tr[7000010];
    ll root[1000010], cnt;

    //	初始化fa数组
    void build_dsu_fa(ll &rt, ll l, ll r) {
        if (!rt)
            rt = ++cnt;

        if (l == r) {
            tr[rt].val = l;
            return;
        }

        ll mid = l + ((r - l) >> 1);
        build_dsu_fa(tr[rt].lson, l, mid);
        build_dsu_fa(tr[rt].rson, mid + 1, r);
    }

    //	初始化dep数组
    void build_dsu_dep(ll &rt, ll l, ll r) {
        if (!rt)
            rt = ++cnt;

        if (l == r) {
            tr[rt].val = 1;
            return;
        }

        ll mid = l + ((r - l) >> 1);
        build_dsu_dep(tr[rt].lson, l, mid);
        build_dsu_dep(tr[rt].rson, mid + 1, r);
    }
    //	本题中无用
    void build_tree(ll &rt, ll l, ll r, ll pos, ll key) {
        if (!rt)
            rt = ++cnt;

        if (l == r) {
            tr[rt].val = key;
            return;
        }

        ll mid = l + ((r - l) >> 1);
        if (pos <= mid)
            build_tree(tr[rt].lson, l, mid, pos, key);
        else
            build_tree(tr[rt].rson, mid + 1, r, pos, key);
    }

    void update(ll &rt, ll pre, ll l, ll r, ll pos,
                ll key) { // 修改操作：将pos位置的值改为key
        rt = ++cnt;

        if (l == r) {
            tr[rt].val = key;
            return;
        }

        ll mid = l + ((r - l) >> 1);
        if (pos <= mid) {
            tr[rt].rson = tr[pre].rson;
            update(tr[rt].lson, tr[pre].lson, l, mid, pos, key);
        } else {
            tr[rt].lson = tr[pre].lson;
            update(tr[rt].rson, tr[pre].rson, mid + 1, r, pos, key);
        }
    }

    //	查询某一位置的值
    ll query(ll rt, ll l, ll r, ll pos) {
        if (l == r)
            return tr[rt].val;

        ll mid = l + ((r - l) >> 1);
        if (pos <= mid)
            return query(tr[rt].lson, l, mid, pos);
        else
            return query(tr[rt].rson, mid + 1, r, pos);
    }

    //	获取集合的根节点
    ll get_fa(ll ver, ll pos) {
        ll fa = query(root[ver], 1, n, pos);
        if (fa == pos)
            return fa;
        return get_fa(ver, fa);
    }

    //	判断是否在同一集合
    ll dsu_judge(ll ver, ll x, ll y) {
        ll a = get_fa(ver, x), b = get_fa(ver, y);
        return a == b;
    }

    Array() {}
};

Array fa, dep;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;

    fa.build_dsu_fa(fa.root[0], 1, n);
    dep.build_dsu_dep(dep.root[0], 1, n);

    ll op, a, b;
    for (int i = 1; i <= m; i++) {
        cin >> op;
        if (op == 1) {
            cin >> a >> b;
            a = fa.get_fa(i - 1, a);
            b = fa.get_fa(i - 1, b);
            if (a != b) {
                ll x = dep.query(dep.root[i - 1], 1, n, a),
                   y = dep.query(dep.root[i - 1], 1, n, b);
                if (x < y)
                    swap(x, y), swap(a, b);
                fa.update(fa.root[i], fa.root[i - 1], 1, n, b, a);
                if (x == y)
                    dep.update(dep.root[i], dep.root[i - 1], 1, n, a,
                               x + 1); // 我cnmlg********
                else
                    dep.root[i] = dep.root[i - 1];
            } else {
                fa.root[i] = fa.root[i - 1];
                dep.root[i] = dep.root[i - 1];
            }
        } else if (op == 2) {
            cin >> a;
            fa.root[i] = fa.root[a];
            dep.root[i] = dep.root[a];
        } else if (op == 3) {
            cin >> a >> b;
            fa.root[i] = fa.root[i - 1];
            dep.root[i] = dep.root[i - 1];
            cout << fa.dsu_judge(i, a, b) << '\n';
        }
    }

    cout.flush();

    return 0;
}

注意事项

再说一遍，储存空间的大小一定要保证充足
不能使用路径压缩，这个...... 原因留个阅读这篇笔记的各位思考
一定，一定，一定，一定，不要把按秩合并写假了
一定，一定，一定，一定，不要把按秩合并写假了
一定，一定，一定，一定，不要把按秩合并写假了

可持久化并查集 学习笔记 ​

前置技能 ​

步入正题 —— 可持久化并查集 ​

而，对于 2 操作： ​

AC 代码： ​