• 本文因为做题做颓废了于是上B站学了下这玩意

只因本概念

支持回退，访问之前版本。建立在可持久化数组上。

把 fa 数组可持久化

并查集优化

1. 路径压缩
2. 按秩合并

因为 fa 数组是用可持久化数组维护的，所以就没法用路径压缩了。

因为每次路径压缩时，fa[x] = find(fa[x])，会修改许多次 fa 数组。而每次修改会再创建一个新版本，因此无法路径压缩。

因为每个版本并查集节点深度可能不同，所以我们还需要新开一个可持久化数组记录每个版本的 dep 数组。

代码乱打

const int N = 2e5 + 10;
struct node
{
    int l, r, val;
}t[N * 40 * 2];

int cnt, rfa[N], rdep[N], tot;

int build(int l, int r)
{
    int p = ++ cnt;
    if(l == r)
    {
        t[p].val = ++ tot;
        return p;
    }
    int mid = l + r >> 1;
    t[p].l = build(l, mid);
    t[p].r = build(mid + 1, r);
    return p;
}

int change(int l, int r, int p, int pos, int val)
{
    int q = ++ cnt;
    t[q] = t[p];
    if(l == r)
    {
        t[q].val = val;
        return q;
    }
    int mid = l + r >> 1;
    if(pos <= mid) t[q].l = change(l, mid, t[p].l, pos, val);
    else t[q].r = change(mid + 1, r, t[p].r, pos, val);
    return q;
}

int query(int l, int r, int p, int pos)
{
    if(l == r) return t[p].val;
    int mid = l + r >> 1;
    if(pos <= mid) return query(l, mid, t[p].l, pos);
    else return query(mid + 1, r, t[p].r, pos);
}

int find(int p, int x)
{
    int fx = query(1, n, rfa[p], x);
    return fx == x ? x : find(p, fx);
}

void merge(int p, int x, int y)
{
    x = find(p - 1, x);
    y = find(p - 1, y);
    if(x == y)
    {
        rfa[p] = rfa[p - 1];
        rdep[p] = rdep[p - 1];
    }
    else
    {
        int depx = query(1, n, rdep[p - 1], x);
        int depy = query(1, n, rdep[p - 1], y);
        if(depx < depy)
        {
            rfa[p] = change(1, n, rfa[p - 1], x, y);
            rdep[p] = rdep[p - 1];
        }
        else if(depx > depy)
        {
            rfa[p] = change(1, n, rfa[p - 1], y, x);
            rdep[p] = rdep[p - 1];
        }
        else
        {
            rfa[p] = change(1, n, rfa[p - 1, x, y]);
            rdep[p] = change(1, n, rdep[p - 1], y, depy + 1)
        }
    }
}

int main()
{
    cin >> n >> m;
    rfa[0] = build(1, n);

    for(int ver = 1; ver <= m; ver ++)
    {
        int op, x, y;
        cin >> op;
        if(op == 1)
        {
            cin >> x >> y;
            merge(ver, x, y);
        }
        else if(op == 2)
        {
            cin >> x;
            rfa[ver] = rfa[x];
            rdep[ver] = rdep[x];
        }
        else 
        {
            cin >> x >> y;
            rfa[ver] = rfa[ver - 1];
            rdep[ver] = rdep[ver - 1];
            int fx = find(ver, x), fy = find(ver, y);
            if(fx == fy) cout << 1 << endl;
            else cout << 0 << endl;
        }
    }
}