这题卡不卡 Splay?

Isshiki·Iroha @ 2021-10-10 15:13:13

by LawrenceSivan @ 2021-10-10 15:18:36

@Isshiki·Iroha 为啥要卡啊

by Isshiki·Iroha @ 2021-10-10 15:28:40

@LawrenceSivan

是卡像树状数组加二分这样的吗？

by Echidna @ 2021-10-10 15:30:09

@Isshiki·Iroha 主要卡的是 trie

by LawrenceSivan @ 2021-10-10 15:31:30

@Isshiki·Iroha 树状数组二分要离线的吧

by Isshiki·Iroha @ 2021-10-10 15:33:46

@LawrenceSivan

离线还有离散化，普通版的我好像树状数组二分 O(n^2) 搞过去了

by Isshiki·Iroha @ 2021-10-10 15:34:17

@某学oi的蒟蒻

Trie 能过吧，第一篇题解就是 Trie

by Echidna @ 2021-10-10 15:36:02

@Isshiki·Iroha 能过

但是只能过一点（指很难通过）

by LawrenceSivan @ 2021-10-10 15:36:08

@Isshiki·Iroha 这题强制在线啊，还有你这是咋算了个 \mathcal{O(n^2)} 的

by Isshiki·Iroha @ 2021-10-10 15:36:42

@LawrenceSivan

我查 Pre 和 Nxt 是线性的扫过去

by Isshiki·Iroha @ 2021-10-10 15:38:10

话说查排名为 x 的数，树状数组二分是 O(\log^2 n) 吗