「学习笔记」可持久化并查集 / rope

我们来看一下可持久化并查集

(有是玄学数据结构

(其实用STL里面的rope就可以了quq


我们来看看一种基于cheatcheat的思想:

UVA 11987 Almost Union-Find

要求把一个元素从一个集合中剥离的情况,我们只需要新建一个节点然后………乱搞即可

还是看代码吧:

1
2
3
4
5
6
7
8
inline void move(int x,int y)     // 把x从y集合中剥离
{
int fx = find(id[x]),fy = find(id[y]);
if(fx == fy) return ;
cnt[fx] --,sum[fx] -= x;
id[x] = ++ tot; // 可持久化
f[id[x]] = fy; cnt[fy] ++,sum[fy] += x;
}

这种方法主要是利用idid,在最初时idi=iid_i = i,随着移动iiidiid_i也在变化,在访问ii时,我们需直接用idiid_i代替。

于是我们带着这个思路看到了BZOJ 3673这道题

看到题目 \rightarrow mengbier \rightarrow ......试图乱搞 \rightarrow 爆炸

可持久化并查集加强版 我们就不能cheatcheat了,我们需要真的可持久化了

因为并查集的所有信息都保存在fafa里,所以,我们只需要用可持久化线段树实现一个可持久化数组并使其启发式合并就可以了

并查集的启发式合并就是按秩合并,初始所有集合秩为00

合并把秩小的树根的父亲设为秩大的树根

如果秩相同,则随便选取一个作为父节点并将它的秩+1+1,秩和fafa一样维护

但是其实这题数据随机的话随便合并就行了,根本不用按秩合并什么的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
//
// Code from hzwer.com
// http://hzwer.com/3951.html
//
#include<iostream>
#include<cstdio>
using namespace std;
inline int read()
{
int x=0;char ch=getchar();
while(ch>'9'||ch<'0')ch=getchar();
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int n,m,sz;
int root[200005],ls[2000005],rs[2000005],v[2000005],deep[2000005];
void build(int &k,int l,int r)
{
if(!k)k=++sz;
if(l==r){v[k]=l;return;}
int mid=(l+r)>>1;
build(ls[k],l,mid);
build(rs[k],mid+1,r);
}
void modify(int l,int r,int x,int &y,int pos,int val)
{
y=++sz;
if(l==r){v[y]=val;deep[y]=deep[x];return;}
ls[y]=ls[x];rs[y]=rs[x];
int mid=(l+r)>>1;
if(pos<=mid)
modify(l,mid,ls[x],ls[y],pos,val);
else modify(mid+1,r,rs[x],rs[y],pos,val);
}
int query(int k,int l,int r,int pos)
{
if(l==r)return k;
int mid=(l+r)>>1;
if(pos<=mid)return query(ls[k],l,mid,pos);
else return query(rs[k],mid+1,r,pos);
}
void add(int k,int l,int r,int pos)
{
if(l==r){deep[k]++;return;}
int mid=(l+r)>>1;
if(pos<=mid)add(ls[k],l,mid,pos);
else add(rs[k],mid+1,r,pos);
}
int find(int k,int x)
{
int p=query(k,1,n,x);
if(x==v[p])return p;
return find(k,v[p]);
}
int main()
{
n=read();m=read();
build(root[0],1,n);
int f,k,a,b;
for(int i=1;i<=m;i++)
{
f=read();
if(f==1)
{
root[i]=root[i-1];
a=read();b=read();
int p=find(root[i],a),q=find(root[i],b);
if(v[p]==v[q])continue;
if(deep[p]>deep[q])swap(p,q);
modify(1,n,root[i-1],root[i],v[p],v[q]);
if(deep[p]==deep[q])add(root[i],1,n,v[q]);
}
if(f==2)
{k=read();root[i]=root[k];}
if(f==3)
{
root[i]=root[i-1];
a=read();b=read();
int p=find(root[i],a),q=find(root[i],b);
if(v[p]==v[q])puts("1");
else puts("0");
}
}
return 0;
}

但是这样就够了吗?

想象一下你在考场里,

  1. 时间不够,写不出可持久化并查集的正解
  2. 在短时间内写出暴力对拍程序
  3. 给不会STL,rope,可持久化并查集的人(学弟/学妹)装逼

这时候你就需要rope这种神奇的东西了

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <ext/rope>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <ctime>

using namespace __gnu_cxx;

const int maxm = 120010;

rope<int> *fa[maxm];
int a[maxm],lastans;
int n,m;

int find(int i,int x) {
if(fa[i]->at(x) == x) return x;
int f = find(i,fa[i]->at(x));
if(f == fa[i]->at(x)) return f;
fa[i]->replace(x,f);
return fa[i]->at(x);
}

inline void merge(int i,int x,int y) {
x = find(i,x),y = find(i,y);
if(x != y) fa[i]->replace(y,x);
}

int SlowRead(){
int data = 0, w = 1;
char ch = 0;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while (ch >= '0' && ch <= '9') data = (data << 1) + (data << 3) + ch - '0', ch = getchar();
return data * w;
}

int main(int argc, char const *argv[]) {
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) a[i] = i;
fa[0] = new rope<int> (a, a + n + 1);
for(int i = 1; i <= m; i++) {
fa[i] = new rope<int> (*fa[i - 1]);
int opt = SlowRead();
if(opt == 1) {
int a = SlowRead(),b = SlowRead();
merge(i, a, b);
} else if(opt == 2) {
int k = SlowRead();
fa[i] = fa[k];
} else {
int a = SlowRead(),b = SlowRead();
printf("%d\n",lastans = (find (i, a) == find (i, b)));
}
}
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!