怎么卡单旋 WBT/WBLT 啊?

P6136 【模板】普通平衡树(数据加强版)

Cat_shao @ 2022-08-13 10:56:32

如题。我不会卡。

很容易造出数据使得单旋 WBT 的树高并非 \Theta(\log n) ,但是怎么把树高卡到 \Theta(n) 我就不会了。有没有大佬教教我?

顺便再加强下这题数据。

https://www.luogu.com.cn/problem/U237900

求管理把里面的数据全加到本题的数据中,谢谢。


by Cat_shao @ 2022-08-13 10:58:43

@一扶苏一 , @_bzy ,@WYXkk , @小粉兔 , @ezoixx130 , @yurzhang , @JohnVictor , @离散小波变换°


by Cat_shao @ 2022-08-13 10:58:58

@一扶苏一 @小粉兔 @离散小波变换°


by irris @ 2022-08-13 10:59:37

@Cat_shao 哥们,你 at 这么多管理是干嘛/qd


by Cat_shao @ 2022-08-13 11:01:42

@AlgorithmerSnow 一般只有小波一个人来。。。别的管理都在睡大觉

不多 at 点感觉得沉贴。


by 一扶苏一 @ 2022-08-13 12:23:41

巧了,这次我没睡,刚熬了个通宵


by 一扶苏一 @ 2022-08-13 12:42:49

@Cat_shao 这些 hack 全加上以后数据点有点偏多……请您确认一下是否有些 hack 是可合并的之类的……如果不行我再想想办法 /kel


by Cat_shao @ 2022-08-13 14:50:42

@一扶苏一 确实。您先等等。


by Cat_shao @ 2022-08-13 16:45:30

@一扶苏一 建议把那后 9 个 hack 撤了,是我 hack 的。有时间我把 hack splay 的整成一个测试点。

顺便问下原数据在卡啥?


by Cat_shao @ 2022-08-13 16:46:06

后九个指的是后加的九个 ,是 subtask 1 中的 9 个。


by 一扶苏一 @ 2022-08-13 22:39:51

@Cat_shao 没懂啊,我没在您给的那个题里看到 subtask 1


| 下一页