【bzoj3674】可持久化并查集加强版

2014年8月2日5,40013

Description

Description:
自从zkysb出了可持久化并查集后……
hzwer:乱写能AC,暴力踩标程
KuribohG:我不路径压缩就过了!
ndsf:暴力就可以轻松虐!
zky:……

n个集合 m个操作
操作:
1 a b 合并a,b所在集合
2 k 回到第k次操作之后的状态(查询算作操作)
3 a b 询问a,b是否属于同一集合,是则输出1否则输出0
请注意本题采用强制在线,所给的a,b,k均经过加密,加密方法为x = x xor lastans,lastans的初始值为0
0<n,m<=2*10^5

Sample Input

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

Sample Output

1
0
1

题解

听说zky把我的做法卡了2333

然后我T的停不下来。。。注意看了眼题目,诶强制在线。。。

再次T的停不下来T T,开大了空间准备开始写路径压缩,恩先随手交一下吧。。。

诶A掉了

原来是zky大神卡我程序忘记开大数组了T T

发现似乎加上路径压缩之后时间变慢了T T

 

  • 张凯羿2014年8月2日 下午8:13 回复

    噗……原来用您的程序卡的时候忘开大数组了,我果然是真·弱逼

    #1  
  • KuribohG2014年8月2日 下午8:40 回复

    貌似无所谓……路径压缩好像根本没用

    #2  
    • maoxiaohan19992014年8月3日 上午8:43 回复

      其实是出题人没有卡掉。

      #21
      • KuribohG2014年8月3日 下午7:14 回复

        只需要按秩合并,是卡不掉的

        #22
        • maoxiaohan19992014年8月5日 上午8:34 回复

          只要把多出来的log卡掉就行了(不过可能会不小心把正解卡掉?)

          #23
          • hzwer2014年8月5日 上午10:24
            admin

            T T 这个不好卡吧

            #24
          • maoxiaohan19992014年8月5日 上午10:34

            说实话再丧心病狂一点可以这样:把只用路径压缩||只用按秩合并的全部卡掉……不过为了noip还是攒点人品吧(其实是我自己弱造不出这样的数据)

            #24
          • hzwer2014年8月5日 上午10:39
            admin

            这样仅仅是理论复杂度减小了T T

            #24
          • hzwhzw?hzwhzw!2016年1月2日 上午10:39

            然而Noip2015 Day2T3的理论复杂度。。。

            #24
  • yz232015年6月29日 下午5:11 回复

    黄学长:请问只写启发式合并和只写路径压缩哪个更快?还有启发式合并的关键字不是最长链的长度吗(考虑最劣情况)?
    srO谢谢Orz

    #3  
    • hzwer2015年6月29日 下午9:57 回复
      admin

      数据使然?由于你每次都是启发式合并所以最长链长度不科学吧

      #31
      • YZ232015年6月30日 下午5:37 回复

        然而每次相当于插入一个点,感觉和子树大小没啥关系。。

        #32
        • hzwer2015年6月30日 下午8:55 回复
          admin

          都是启发式合并啊,合出来的东西就像个满二叉树

          #33