我树套树四秒
by LHQing @ 2021-12-24 20:56:36
@[Tyyyyyy](/user/333574) 树套树的 kth 操作是 $\mathcal{O}(\log^3n)$ 的吧。。
by rui_er @ 2021-12-24 20:57:03
resub 以前的树套树 AC 代码发现开 O2 都过不去了，被卡常了一个点，，
by rui_er @ 2021-12-24 20:59:20
分块YYDS！！
by jockbutt @ 2021-12-24 21:01:24
大胜利！
by ctldragon @ 2021-12-24 21:03:29
@[rui_er](/user/122461) 可以 $O(\log^2n)$ 把。
by rxjdasiwzl @ 2021-12-24 21:06:45
我 7 月份 889ms 的代码重新交一次变成了 2.51s，不知道什么原理。
by xyf007 @ 2021-12-24 21:11:03
树状数组套权值线段树就是单次 $O(\log^2n)$ 的。
by rxjdasiwzl @ 2021-12-24 21:11:47
其实挺正常的，毕竟分块小常数很难跑满，树套树不但几乎全部跑满还有大概四倍的常数
by FunnyCreatress @ 2021-12-24 21:21:21
@[rui_er](/user/122461) 那个3log的做法是大暴力，有更高明的2log
by Prean @ 2021-12-24 21:24:28