题解 铃音的第二分块

· · 题解

显然该问题不弱于区间加区间 rank，考虑 $O(n\sqrt n)$ 做法。 对值域 $b$ 为底数分块，即块为 $[b^0,b^1),[b^1,b^2)\dots$，每块维护值域在该块内的数，共有 $\log_b v=\dfrac w {\log b}$ 块。 取常数 $k>0$，令 $b=n^k$，则共有 $\dfrac w {\log b}=\dfrac w {k\log n}=O(\dfrac 1 k)$ 块。 即 $O(1)$ 块。 容易发现，每次存在三种情形： 1. 不变 2. 被减去 $x$，但所属块不变 3. 被减去 $x$，所属块变 显然，对于 $x$ 所属的块会发生三种情形。该块内的数显然经过 $O(b)$ 次情形 $2$ 后就会发生情形 $3$。对于每个数会发生 $O(1)$ 次情形 $3$，那么会发生 $O(b)$ 次情形 $2$。 对小于 $x$ 的块只会发生情形 $1$，忽略。对大于 $x$ 的块会发生情形 $2,3$。 对块维护线段树，可以识别三种情形的发生。 那么问题其实是： 1. $O(nb)$ 次单点修改（情形 $2$） 2. $O(n)$ 次区间 rank（查询） 3. $O(n)$ 次区间减（情形 $3$） 我们希望做到 $O(n\sqrt n)$，那么操作 $1$ 需要 $o(\sqrt n)$。 对序列分块，块长为 $\Theta(\sqrt n)$。每次单点修改累计在一个块内，用另一个数据结构用同样的分块结构进行维护，直到该块内有 $b$ 次单点修改就对原块进行重构。 用线段树上分散层叠维护，这是 well-known 的。单点修改用另一个数据结构维护时需要抵消原数贡献。另一个数据结构中每块有 $O(b)$ 个数，每 $\Theta(b)$ 次修改重构该块，同样用线段树上分散层叠维护，修改时间复杂度 $O(b)$，查询时间复杂度 $O(\sqrt n)$，重构单块次数为 $O(n)$，所以重构时间复杂度为 $O(n\sqrt n)$。这里大小为 $O(b)$ 的分块起到了缓存的作用。 时间复杂度 $O(n\sqrt n+nb^2)$，取 $k\in(0,0.25]$ 即可 $O(n\sqrt n)$。 于是我们解决了问题，甚至在线线性空间。 实际实现使用的是平凡的二分做法，时间复杂度 $O(n\sqrt{n\log n})$，因为分散层叠的常数会和 $4\log_n w$ 相乘，大概不能要了，二分反而能微调块长。