P3402 【模板】可持久化并查集
题目描述
n个集合 m个操作
操作：
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合，是则输出1否则输出0
说明
1 ≤ n ≤ 105,1 ≤ m ≤ 2×105
By zky 出题人大神犇
基本和上午那道题一模一样了？？重新写一下思路清晰很多，也发现了很多细节。
一定要用启发式合并，就是维护siz，小的那一块合并到大的那一块去，这样保证小的每次乘2，保证了复杂度log级。不然会T得很惨QAQ
还有就是空间一定要开足，在并查集find操作里面不能路径压缩，如果压缩每次都会多log的空间复杂度，因为保证深度是log，所以不用担心时间复杂度。
合并时先找到两点的fa再做下一步处理，包括判断siz大小等。
#include<bits/stdc++.h>
using namespace std;
int n, m;
void read(int &x) {
x = 0; char ch = getchar();
while(ch > '9' || ch < '0') ch = getchar();
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
}
struct Node {
Node *ls, *rs;
int fa, pos, siz;
} pool[200005*32], *tail = pool, *root[200005], *zero;
Node *newnode() {
Node *nd = ++ tail;
nd -> ls = zero;
nd -> rs = zero;
nd -> fa = nd -> pos = nd -> siz = 0;
return nd;
}
Node *build(int l, int r) {
Node *nd = newnode();
if(l == r) {
nd -> fa = l;
nd -> siz = 1;
nd -> pos = l;
return nd;
}
int mid = (l + r) >> 1;
nd -> ls = build(l, mid);
nd -> rs = build(mid + 1, r);
return nd;
}
Node *Query(Node *nd, int l, int r, int pos) {
if(l == r) return nd;
int mid = (l + r) >> 1;
if(pos <= mid) return Query(nd -> ls, l, mid, pos);
else return Query(nd -> rs, mid + 1, r, pos);
}
int find(Node *nd, int x) {
int a = Query(nd, 1, n, x) -> fa;
if(a != x) return find(nd, a);
return a;
}
Node *Modify(Node *nd, int l, int r, int pos, int f) {
Node *nnd = newnode();
if(l == r) {
nnd -> siz = nd -> siz; nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> pos = nd -> pos;
nnd -> fa = f;
return nnd;
}
int mid = (l + r) >> 1;
if(pos <= mid) {
nnd -> rs = nd -> rs;
nnd -> ls = Modify(nd -> ls, l, mid, pos, f);
} else {
nnd -> ls = nd -> ls;
nnd -> rs = Modify(nd -> rs, mid + 1, r, pos, f);
}
return nnd;
}
Node *Change(Node *nd, int l, int r, int pos, int siz) {
Node *nnd = newnode();
if(l == r) {
nnd -> fa = nd -> fa; nnd -> ls = nd -> ls; nnd -> rs = nd -> rs; nnd -> pos = nd -> pos;
nnd -> siz = siz;
return nnd;
}
int mid = (l + r) >> 1;
if(pos <= mid) {
nnd -> rs = nd -> rs;
nnd -> ls = Change(nd -> ls, l, mid, pos, siz);
} else {
nnd -> ls = nd -> ls;
nnd -> rs = Change(nd -> rs, mid + 1, r, pos, siz);
}
return nnd;
}
int main() {
scanf("%d%d", &n, &m);
zero = ++ tail;
zero -> ls = zero, zero -> rs = zero, zero -> fa = 0, zero -> pos = 0, zero -> siz = 0;
root[0] = build(1, n);
for(int i = 1; i <= m; i ++) {
int opt;
read(opt);
if(opt == 1) {
int a, b;
read(a); read(b);
int u = find(root[i-1], a);
int v = find(root[i-1], b);
Node *uu = Query(root[i-1], 1, n, u);
Node *vv = Query(root[i-1], 1, n, v);
if(uu -> siz > vv -> siz) swap(uu, vv);
root[i] = Modify(root[i-1], 1, n, uu -> pos, vv -> pos);
root[i] = Change(root[i], 1, n, vv -> pos, vv -> siz + uu -> siz);
} else if(opt == 2) {
int a;
read(a);
root[i] = root[a];
} else {
int a, b;
read(a); read(b);
int u = find(root[i-1], a);
int v = find(root[i-1], b);
if(u == v) printf("1
");
else printf("0
");
root[i] = root[i-1];
}
}
return 0;
}