BZOJ [3673/3674] [可持久化并查集 by zky]/[可持久化并查集加强版]

发布于 2017-07-04  167 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3673

                 http://www.lydsy.com/JudgeOnline/problem.php?id=3674

题意:n 个集合 m 个操作

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


通过主席树可以实现 可持久化数组 ,并查集其实就是记录了一个 fa... 那么可持久化 fa 一下就是可持久化并查集了...

加强版什么的... 由于是非离线做法也没有影响,开大空间即可 orz

3673:

3674:

 


一个非常弱的准退役OIER