实测将按秩合并的估价改为集合高度可以通过 hack
估计是 size 作估价不够优秀吧...
by fanypcd @ 2022-01-22 11:18:02
@[违规用户名pbFH$J9W](/user/90027) 本来按大小合并就不是按秩合并啊,是启发式合并,但是应该是能过的。
by rxjdasiwzl @ 2022-01-22 11:20:50
按秩合并本来就是比较深度的吧
by 7KByte @ 2022-01-22 11:21:15
@[rxjdasiwzl](/user/96446) 启发式合并是假的,我可以多次询问一个很深的节点,而启发式合并只统计了合并的复杂度
by 7KByte @ 2022-01-22 11:22:13
@[7KByte](/user/119261) 但是不是跳一次大小乘二吗?
by rxjdasiwzl @ 2022-01-22 11:24:28
@[rxjdasiwzl](/user/96446) 并不是所有边都跳一次乘二,一些重儿子对应的边就不是
by 7KByte @ 2022-01-22 11:29:50
@[7KByte](/user/119261) 但是考虑合并的时候,只有一个子树深度全体加一,启发式合并是让小的子树全体加一,依然满足这个性质?
by rxjdasiwzl @ 2022-01-22 11:41:01
@[rxjdasiwzl](/user/96446) 有道理,那我就不知是怎么卡的了
by 7KByte @ 2022-01-22 11:48:39
这题按 sz 合并能过吧?
by Aestas16 @ 2022-01-22 11:49:39
@[Aestas16](/user/128141) 我按sz的写法十分优秀地过了啊.
by LHQing @ 2022-01-23 11:26:29