自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:43:55，当前版本为作者最后更新于2022-11-14 21:11:40，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$w=\Theta(\log n)$，$O(n\sqrt n)$。

显然该问题不弱于区间加区间 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$ 相乘，大概不能要了，二分反而能微调块长。