关于splay被卡的一句心得

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

345678910jqka @ 2022-09-27 20:43:21

操作4查rank时因为直接根据size查所以没有splay返回节点,事实证明这里splay一下返回节点有助于过题(#9 3.20s -> 385ms)


by 345678910jqka @ 2022-09-27 20:43:49

谁来教教我怎么在评论区写markdown(刚回归,不熟悉操作)


by LHQing @ 2022-09-27 20:54:02

第九个点确实如此,求这个是如何造数据卡不splay的。


by juruo999 @ 2022-09-27 20:54:58

@345678910jqka 这里不 splay 复杂度是不对的(?)


by LHQing @ 2022-09-27 20:58:25

@juruo999 复杂度确实不对,可是如何构造数据卡呢。


by juruo999 @ 2022-09-27 21:00:28

@LHQing 比如依次插入 1,2,\cdots,n 再查询 很多次 1


by LHQing @ 2022-09-27 21:02:23

@juruo999 哦确实


by 345678910jqka @ 2022-09-28 15:30:31

orz


|