ppip @ 2022-05-06 21:35:58
每个点最多缩一次，压缩完就 O(1)，摊还不是 O(1) 的吗
还是merge可以诡异的增加压缩次数？
求好理解的解答qwq
by 年年有年 @ 2022-05-06 21:36:42
认真想想，每个点最多缩一次吗。
by 黑影洞人 @ 2022-05-06 21:36:53
@ppip 我记得是反哈夫曼函数
by 3a51_ @ 2022-05-06 21:37:16
哦我傻了
by 年年有年 @ 2022-05-06 21:37:38
反哈夫曼函数。
by Acc_Robin @ 2022-05-06 21:37:43
如果所有查询都在合并之后，每个点才只缩一次吧
by w23c3c3 @ 2022-05-06 21:37:56
路径压缩会被卡到一只 log。
网上搜搜有构造的。
by ppip @ 2022-05-06 21:37:57
@黑影洞人 ？单独用路径压缩不是 log 的吗
by Acc_Robin @ 2022-05-06 21:38:13
反阿克曼函数。
by monstersqwq @ 2022-05-06 21:42:27
路径压缩不是1log吗。
by P8107 @ 2022-05-06 21:48:09
单独路径压缩和按秩合并都是logn，和一起用才是反阿克曼