「BZOJ3674」可持久化并查集加强版

2014年8月2日7,12815

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

 

说点什么

提醒
avatar
ViXbob

黄学长您那个add函数修改深度是不是有问题啊,修改深度应该在当前版本新开一条链再修改,而您却是修改上一个版本的深度

sss

    [spoiler title=” “]`
yz23
yz23

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

KuribohG
KuribohG

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

maoxiaohan1999

其实是出题人没有卡掉。

KuribohG
KuribohG

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

maoxiaohan1999

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

maoxiaohan1999

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

hzwhzw?hzwhzw!
hzwhzw?hzwhzw!

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

张凯羿

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