玄学代码求解释

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

THUD @ 2024-06-25 21:28:30

由于含满分代码代码不公开,正常来说加了代码公开计划的都看得到\ 代码1 这份代码在第#6 #7上TLE了\ 代码2 然而这份代码AC了\ 唯一的改动就是将查询前驱、后继的操作由"查询左子树的最右儿子"等操作改为了使用排名与第k大元素的组合表示,理应来说这两种写法都splay了两次,复杂度也没多大变化,不知为何时间会有差距,求各位大佬解释


by THUD @ 2024-06-26 11:41:38

补充:注意这两份代码在#6 #7上运行时间差距有30倍左右,不排除死循环


by THUD @ 2024-06-27 19:45:41

record 在查前驱后继后加了splay过了,但是还是不理解,毕竟erase操作也splay了。而且加了splay后直接从>3.20s降到136ms(但是还是比代码2要慢),个人感觉不会差这么多,求解释


|