事实证明，《普通平衡树》是无法卡掉非平衡树做法的

P6136 【模板】普通平衡树（数据加强版）

VictorYuan @ 2020-02-28 11:26:29

在非加强版中， 01tire，权值树状数组/线段树，vector表现优秀，而在本题中，这三种做法均可通过一定的优化AC,01tire和权值树状数组的优化前面已经有人提了，我在题解里放上了自己的vector做法。

由此可见，非加强版能过的非平衡树做法，本题中几乎都可以通过一些优化过掉。

by HsKr @ 2020-02-28 11:27:13

%%%

by Rainbow_qwq @ 2020-02-28 11:27:47

orz

by 皎月半洒花 @ 2020-02-28 11:28:21

但至少这题也让大家知道了许多更进阶的做法吧。毕竟原来那题没人关心这些。

by BFqwq @ 2020-02-28 11:31:11

其实这个题本来就没有必要完全卡掉这些做法，毕竟在正式比赛的时候人家只关心你对不对，不关心你到底用的是不是平衡树。

当然加强数据是有必要的，以前的数据的确有点过水了（

by BFqwq @ 2020-02-28 11:33:05

而且一加强之后发现反而splay这种没占到优势，经常T几个点（

by tuxiaobei @ 2020-02-28 11:38:31

@世界第一肥宅BF +1

这题本来就是模板题，又不是比赛题，能验证算法正确性就可以了，自己想写什么算法就写什么，越多算法通过反而不是什么坏事

by 142857cs @ 2020-02-28 11:45:43

要卡01trie可能要区间翻转

vector我还是觉得该卡

树状数组怎么优化我还没看

by FZzzz @ 2020-02-28 11:45:49

取块长 \sqrt{nw} 总复杂度大概是 \frac{n\sqrt{nw}}{w}？似乎在平衡树跑得动的范围内不是很好卡……

by FZzzz @ 2020-02-28 11:46:47

您成功把一个简单的平衡树题搞成了一个神奇的根号问题

by hly1204 @ 2020-02-28 11:47:58

出题人没想卡，不是卡不了吧？

| 下一页