感觉有 Treap 那味？
by Rubidium_Chloride @ 2022-02-10 19:30:22
这个好像很早就有人提出来过了（指我看到在洛谷），据说当时有一个证明（
by UnyieldingTrilobite @ 2022-02-10 19:31:15
可以交一下板子题？我上次也写了个随机 merge 被板子卡了（
by monstersqwq @ 2022-02-10 19:31:27
@[monstersqwq](/user/191868) 模板题跑飞快（（
by ethan_zhou @ 2022-02-10 19:36:14
@[monstersqwq](/user/191868) 我和您的写法似乎不太一样，我是判根的rnd值
by ethan_zhou @ 2022-02-10 19:37:41
我记得 uoj 群还是啥群聊过这个，结果是期望复杂度是对的（？）
by 摸鱼酱 @ 2022-02-10 19:38:31
如果没有随机权值，那么每爬一次父亲 size * 2 ，所以做多爬 log 次。
随机权值可以看成每次以 0.5 的概率 size * 2，0.5 的概率没有 *2，但是 size 不减，所以期望就是 *1.5，复杂度大概是 $\log_{\frac{3}{2}}N$，两到三倍常数。
~~以上全是瞎说~~（
by 7KByte @ 2022-02-10 19:41:14
@[摸鱼酱](/user/173685) 以后带撤销的就这么写了，用得爽哈哈（（
by ethan_zhou @ 2022-02-10 19:42:30
@[7KByte](/user/119261) thx
by ethan_zhou @ 2022-02-10 20:02:04
[这个？](https://www.luogu.com.cn/discuss/353526)
@[ethan_zhou](/user/124740)
by peterwuyihong @ 2022-02-10 20:33:54