treap 树高不稳定，可能比 log 大一点。
by CodingJellyfish @ 2021-12-22 17:13:44
@[DoctorJellyfish](/user/52381) 可持久化treap?
by Tom俩 @ 2021-12-22 17:15:02
存在单次操作多次split
by Neph @ 2021-12-22 17:15:23
@[DoctorJellyfish](/user/52381) 请问最坏能够达到多少啊。。。，根本不知道开多大
by 最後の祈りを @ 2021-12-22 17:15:49
@[cirro](/user/147394) 有道理
by CodingJellyfish @ 2021-12-22 17:16:19
如果这样的话就大概是 2logn + 10 以上吧。
by CodingJellyfish @ 2021-12-22 17:17:39
没仔细算，上界也许在 $4$ 左右（split 2，pushdown 2），或者哪里有遗漏我也不清楚。实际上一般按心情开了。
by Miko35 @ 2021-12-22 17:25:25
@[DoctorJellyfish](/user/52381) 可实际5e5的$O(qlogn)$我能达到2.38e7,而ceil-log2(5e5)=19，对应实际的47.5左右，刚好是2logn+10，最坏情况下指不定会炸吧，最坏复杂度我也不会证，达到2倍log可以理解，搞不懂为什么会超过2倍log
by 最後の祈りを @ 2021-12-22 17:26:24
@[Cirno_9](/user/78372) 请问pushdown的2具体是指什么啊，模版题不需要pushdown吧，我理解错了吗
by 最後の祈りを @ 2021-12-22 17:28:46
@[最後の祈りを](/user/389985) 啊抱歉，我写的是另一道模板题 >_<
能看下您的实现吗，常数很大一部分取决于具体实现的
by Miko35 @ 2021-12-22 17:30:28