可持久化并查集 可持久化数组 + 并查集

可持久化并查集

没有想到 这么好写 就是用可持久化数组 维护了 我们并查集 之前的fa 数字 和 dep 数组

从历史版本 合并 查询
当然 这里我们不能路径压缩 只能 安秩合并 降低复杂度
路径压缩复杂度是均摊的，无法可持久化(复杂度可以被卡成暴力)
https://www.acwing.com/problem/content/272/
https://www.luogu.org/problem/P3402

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;

int n, m;
struct node {
	int lc, rc;
	int val, siz;
} tr[maxn * 40];
int tot, root[maxn << 1];

int build(int l, int r) {
	int p = ++ tot;
	if(l == r) {
		tr[p].val = l;
		tr[p].siz = 1;
		return p;
	}
	int mid = l + r >> 1;
	tr[p].lc = build(l, mid);
	tr[p].rc = build(mid + 1, r);
	return p;
}

int updata(int now, int L, int l, int r, int val, int siz) {
	int p = ++ tot;
	tr[p] = tr[now];
	if(l == r) {
		tr[p].val = val;
		tr[p].siz = siz;
		return p;
	}
	int mid = l + r >> 1;
	if(L <= mid) tr[p].lc = updata(tr[now].lc, L, l, mid, val, siz);
	else tr[p].rc = updata(tr[now].rc, L, mid + 1, r, val, siz);
	return p;
}

node query(int now, int L, int l, int r) {
	if(l == r) {
		return tr[now];
	}
	int mid = l + r >> 1;
	if(L <= mid) return query(tr[now].lc, L, l, mid);
	else return query(tr[now].rc, L, mid + 1, r);
}

node finds(int now, int x) {
	node pre = query(now, x, 1, n);
	if(pre.val != x) return finds(now, pre.val);
	return pre;
}

void unions(int k, int last, int a, int b) {
	node x = finds(root[k], a), y = finds(root[k], b);
	if(x.val != y.val) {
		if(x. siz > y.siz) swap(x, y);
		root[k] = updata(root[last], x.val, 1, n, y.val, x.siz);
		root[k] = updata(root[k], y.val, 1, n, y.val, x.siz + y.siz);
	}
}

signed main() {
	scanf("%d %d", &n, &m);
	root[0] = build(1, n);
	int pre = 0;
	for(int i = 1, op, k, a, b; i <= m; ++ i) {
		root[i] = root[i - 1];
		scanf("%d", &op);
		if(op == 1) {
			a ^= pre, b ^= pre;
			scanf("%d %d", &a, &b);
			unions(i, i - 1,a, b);
		} else if(op == 2) {
			scanf("%d", &k);
			k ^= pre;
			root[i] = root[k];
		} else {
			scanf("%d %d", &a, &b);
			a ^= pre, b ^= pre;
			pre = int(finds(root[i], a).val == finds(root[i], b).val);
			printf("%d\n", pre);
		}
	}
	return 0;
}