bzoj 3673可持久化并查集 by zky
程序员文章站
2024-03-02 20:23:40
...
题目:
http://www.lydsy.com/JudgeOnline/problem.php?id=3673
题意:
n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0
0
思路:
可持久化并查集模板题
//并查集实质是一个数组,可持久化并查集就是一个可持久化数组,可以用可持久化线段树维护,本质就是这样
//只有叶子节点维护信息,其他节点都是空
#include <bits/stdc++.h>
using namespace std;
const int N = 20000 + 10, M = 500000 + 10, INF = 0x3f3f3f3f;
int root[N], lson[M], rson[M], par[M], rnk[M];
int tot;
int n;
void build(int l, int r, int &x) //建树,并初始化并查集
{
x = ++tot;
if(l == r)
{
par[x] = l; return;
}
int mid = (l + r) >> 1;
build(l, mid, lson[x]);
build(mid + 1, r, rson[x]);
}
int query(int l, int r, int p, int x) //查询p在当前版本下在树中的编号
{
if(l == r) return x;
int mid = (l + r) >> 1;
if(p <= mid) return query(l, mid, p, lson[x]);
else return query(mid + 1, r, p, rson[x]);
}
void update(int l, int r, int pos, int val, int pre, int &x) //把pos的祖先更新为val
{
x = ++tot;
lson[x] = lson[pre], rson[x] = rson[pre];
if(l == r)
{
par[x] = val, rnk[x] = rnk[pre]; return;
}
int mid = (l + r) >> 1;
if(pos <= mid) update(l, mid, pos, val, lson[pre], lson[x]);
else update(mid + 1, r, pos, val, rson[pre], rson[x]);
}
void add_rnk(int l, int r, int pos, int x)//增加pos的秩
{
if(l == r)
{
rnk[x]++; return;
}
int mid = (l + r) >> 1;
if(pos <= mid) add_rnk(l, mid, pos, lson[x]);
else add_rnk(mid + 1, r, pos, rson[x]);
}
int ufs_find(int p, int x) //找到p所在集合的公共祖先,非递归版
{
int r;
while(true)
{
r = query(1, n, p, x);
if(p == par[r]) break;
p = par[r];
}
return r;
}
//int ufs_find(int p, int x) //找到p所在集合的公共祖先,递归版
//{
// int r = query(1, n, p, x);
// if(p == par[r]) return r;
// else return ufs_find(par[r], x);
//}
//int ufs_find(int p, int x) //找到p所在集合的公共祖先,递归版并压缩路径
//{
// int r = query(1, n, p, x);
// if(p == par[r]) return r;
// int t = ufs_find(par[r], x);
// update(1, n, par[r], t, x, x);//每次压缩路径都要进行一次更新,新建很多节点,数组要开大很多,效率好像也更慢了。。。
// return t;
//}
int main()
{
int m, op, a, b;
scanf("%d%d", &n, &m);
tot = 0;
build(1, n, root[0]);
for(int i = 1; i <= m; i++)
{
scanf("%d", &op);
if(op == 1)
{
root[i] = root[i-1];//版本更新
scanf("%d%d", &a, &b);
int pa = ufs_find(a, root[i-1]), pb = ufs_find(b, root[i-1]);
if(par[pa] == par[pb]) continue;
if(rnk[pa] > rnk[pb]) swap(pa, pb);
update(1, n, par[pa], par[pb], root[i-1], root[i]);
if(rnk[pa] == rnk[pb]) add_rnk(1, n, par[pb], root[i]);
}
else if(op == 2)
{
scanf("%d", &a);
root[i] = root[a];
}
else
{
root[i] = root[i-1];//版本更新
scanf("%d%d", &a, &b);
int pa = ufs_find(a, root[i-1]), pb = ufs_find(b, root[i-1]);
if(par[pa] == par[pb]) puts("1");
else puts("0");
}
}
return 0;
}
上一篇: 可持久化Treap