「BZOJ3673」可持久化并查集 by zky

2014年8月1日24,96516

Description

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0

0<n,m<=2*10^4

Sample Input

5 6
1 1 2
3 1 2
2 0
3 1 2
2 1
3 1 2

Sample Output

1
0
1

题解

这题不知道出题人什么做法,但是代码很短的样子

UPD:出题人用的是rope,即stl中的可持久化平衡树

KuribohG神犇告诉了我可以用可持久化线段树实现可持久化数组T T

 

既然都有可持久化数组了,只要用个再并查集的启发式合并就能妥妥的水过了(这样每次只要修改一个fa)

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

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

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

秩和fa一样维护

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

UPD:秩其实有的时候很不好用,维护子树大小比较赞。。。

另外,ndsf发现只要直接暴力就能虐了T T

 

avatar
7 Comment threads
9 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
5 Comment authors
debuggghzwerCrazyxx索科拉迪斯·帕帕斯塔索普洛斯smkx Recent comment authors
  Subscribe  
提醒
Crazyxx
Crazyxx

既然是可持久化线段树,改了fa又改deep(改了两个点)不就不对了么0.0 求指教

阿蒋

你在modify的时候更新了v数组,但是对于deep数组,你没有继承,只是在deep ==deep 的时候加了1.
导致你的按址合并没有效果了(最多只有1)
如果说错了什么请指导

阿蒋

善良的黄学长,我觉得你写的有问题~
(很可能是本蒟蒻搞错了,勿喷)

索科拉迪斯·帕帕斯塔索普洛斯
索科拉迪斯·帕帕斯塔索普洛斯

Orz KuribohG

张凯羿

敬请期待数据加强版

smkx
smkx

我写了个lct。。。求正解

张凯羿

我是大傻逼……果然被您虐了……