Shunpower @ 2024-01-22 11:07:31
令块长为 B，通过操作分块可以得到一个 \mathcal O(Bn\log n+\frac{q^2}{B}\log n) 的做法。两只 \log 分别来自重构的基于 BIT 和块内修改的贡献需要倍增求 k 级祖先。和这篇题解的第一个做法是一样的。
这个做法确实非常卡，我卡了一个多小时。下面是一些警示后人的方法：
- 把块长改成 \sqrt {q(1+\log q)}，不知道为什么反正就是很快。
- 把重构改成不递归的版本，实测快了非常多。
- 减少树状数组的修改次数。
- 可以把 n^{-1} 之类的常数提出来，不用乘那么多次。
- 实在不行就把 k 级祖先改成长剖。
by Shunpower @ 2024-01-22 11:11:03
前两条针对死活过不了 \texttt{test 6} 和 \texttt{test 17} 很有效。
这里减少修改次数不只是减少外观上的修改次数，加上 0 也要判掉。这对 \texttt{test 71} 很有效。
by Shunpower @ 2024-01-22 11:46:20
@Shunpower 那我知道为什么了，\sqrt {q(1+\log q)} 就是贴着最佳块长 \sqrt{q\log q} 的。