【bzoj3673】可持久化并查集 by zky

2014年8月1日8,60016

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

 

  • 张凯羿2014年8月1日 下午9:53 回复

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

    #1  
    • hzwer2014年8月1日 下午10:02 回复
      admin

      我同学写了个暴力rank1。。。就是直接记下每次修改了哪个fa,直接模拟T T

      #11
      • debuggg2016年6月10日 下午9:01 回复

        fa看着不舒服,应该用gen
        第i个点的父亲节点用gen 不是fa

        #12
  • smkx2014年8月1日 下午10:57 回复

    我写了个lct。。。求正解

    #2  
    • hzwer2014年8月2日 上午1:47 回复
      admin

      是高贵啊T T,暴力就行了

      #21
  • 张凯羿2014年8月2日 上午1:57 回复

    敬请期待数据加强版

    #3  
  • 索科拉迪斯·帕帕斯塔索普洛斯2014年11月8日 下午8:21 回复

    Orz KuribohG

    #4  
  • 阿蒋2014年12月18日 下午6:32 回复

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

    #5  
  • 阿蒋2014年12月18日 下午6:34 回复

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

    #6  
    • hzwer2014年12月18日 下午6:40 回复
      admin

      TAT被您叉了

      #61
    • hzwer2014年12月18日 下午6:46 回复
      admin

      但是改了以后似乎没有变快。。。TAT

      #61
      • 阿蒋2014年12月18日 下午6:48 回复

        233

        #62
        • hzwer2014年12月18日 下午6:49 回复
          admin

          应该就是加一个继承deep吧TAT

          #63
          • 零维度2016年2月9日 下午12:22

            黄学长好。感觉不是很对,因为这棵线段树和前面的线段树有公共部分,所以Add的时候会把前面的线段树的秩改掉
            是不是Add的时候也要新开节点?
            奇怪的是加强版不用deep优化T了QwQ,是我搞错了吗求指教

            #64
  • Crazyxx2015年4月7日 下午12:03 回复

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

    #7  
    • hzwer2015年4月7日 下午1:05 回复
      admin

      每次操作一棵新的树,即这两个操作是在同棵树上。。。

      #71