感觉有 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