disjoint-set

可持久化并查集

题意

给定n个集合，第i个集合初始只有一个数i。有m次操作，操作分为三种：
1 a b 合并a，b所在集合
2 k 回到第k次操作
3 a b 询问a，b是否属于同一集合

题解

简单地说，可持久化并查集其实就是：可持久化线段树+不路径压缩的并查集。

用可持久化线段树存储每个点的父亲节点$fa[i]$，并维护一个$dep[i]$的值表示树高（用于并查集按秩合并）。可持久化线段树有三种操作：

1. build(rt[0], 1, n)：初始化建树操作，初始时将每个值的$fa[i]$赋为$i$，$dep[i]$赋为0。
2. insert(rt[i], rt[i - 1], 1, n, fa, fb)：每个操作1，找到a的父亲fa，b的父亲fb，比较两个父亲的dep值，若dep低的点为fa，则将fa的父亲赋为fb。
3. update(rt[i], 1, n, fb)：如果合并的两个dep值相同，说明合并后的点树高会+1；否则树高小的点不会影响大的点树高。
4. query(rt[i], 1, n, a)：找到操作i时a的父亲
5. Find(rt[i], a)和常规并查集一样不断往上找，但不进行路径压缩。

对于并查集的操作和常规的操作基本一样，只不过在查找时不进行路径压缩，合并时按树高进行合并。

这样按照树高进行合并，最终会接近完全树的形态，每次Find时最多跳$\log n$次数，每次主席树查询也是$\log n$次，总时间复杂度$O(n\log ^ 2 n)$。

代码

/*************************************************************************
> Author: Knowledge_llz
> Link: https://www.luogu.com.cn/problem/P3402 
> 操作1：合并a,b所在集合
> 操作2：回到第k次操作
> 操作3：询问a,b是否在同一集合
************************************************************************/

#include<bits/stdc++.h>
#define LL long long
#define endl '\n'
using namespace std;
const int maxx = 2e5 + 10;
int n, m, f[maxx * 30], dep[maxx * 30], rt[maxx * 30], ls[maxx * 30], rs[maxx * 30], cnt;
void build(int &q, int l, int r){
    q = ++cnt;
    if(l >= r){
        f[q] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(ls[q], l, mid);
    build(rs[q], mid + 1, r);
}
void insert(int &q, int pre, int l, int r, int pos, int fa){
    q = ++cnt; ls[q] = ls[pre]; rs[q] = rs[pre];
    if(l == r){
        f[q] = fa;
        dep[q] = dep[pre];
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) insert(ls[q], ls[pre], l, mid, pos, fa);
    else insert(rs[q], rs[pre], mid + 1, r, pos, fa);
}
void update(int q, int l, int r, int pos){
    if(l == r){
        ++dep[q];
        return;
    }
    int mid = (l + r) >> 1;
    if(pos <= mid) update(ls[q], l, mid, pos);
    else update(rs[q], mid + 1, r, pos);
}
int query(int q, int l, int r, int pos){
    if(l == r) return q;
    int mid = (l + r) >> 1;
    if(pos <= mid) return query(ls[q], l, mid, pos);
    else return query(rs[q], mid + 1, r, pos);
}
int Find(int q, int pos){
    int now = query(q, 1, n, pos);
    if(f[now] == pos) return now;
    else return Find(q, f[now]);
}
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt","w", stdout);
#endif
    cin >> n >> m;
    build(rt[0], 1, n);
    for(int i = 1, t, a, b; i <= m; ++i){
        cin >> t >> a;
        if(t == 1){
            cin >> b;
            rt[i] = rt[i - 1];
            a = Find(rt[i], a), b= Find(rt[i], b);
            if(f[a] != f[b]){
                if(dep[a] > dep[b]) swap(a, b);
                insert(rt[i], rt[i - 1], 1, n, f[a], f[b]);
                if(dep[a] == dep[b]) update(rt[i], 1, n, f[b]);
            }
        }
        else if(t == 2) rt[i] = rt[a];
        else{
            cin >> b;
            rt[i] = rt[i - 1];
            a = Find(rt[i], a); b = Find(rt[i], b);
            cout << (f[a] == f[b]) << endl;
        }
    }
    return 0;
}