自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 21:56:41，当前版本为作者最后更新于2020-03-09 01:17:39，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

第二分块。

我们观察一下这个查询操作。把所有大于 $x$ 的数减去 $x$，相当于把所有小于等于 $x$ 的数加上 $x$，然后全局减 $x$。

我们令 $k$ 表示一个数列中的可能最大值。

若 $2x\geq k$，则我们令大于 $x$ 的数减去 $x$ 之后，就没有比 $x$ 大的数了，则 $k$ 在操作后至少减少 $k-x$。

若 $2x\lt k$，则我们令小于等于 $x$ 的数加上 $x$，就没有比 $x$ 小的数了，然后。打全局减的标记，则 $k$ 在操作后至少减少 $x$。

我们发现不管怎么操作，这个 $k$ 都是单调不增的，而 $k$ 初始最大为 $5\times 10^5$。

所以我们如果是对全局进行修改，按照上面的分析，只需要枚举需要修改的那些数值即可。这里枚举的数值的总和为 $O(n)$（默认 $n,m$ 和值域同阶，下同）。

我们希望对每个不同的值的修改能做到 $O(1)$。

考虑使用并查集把相同的值并起来。那么修改的时候，只需要把修改前值对应的并查集的根，连到修改后的值的并查集的根上即可。同时我们需要记录每个数的出现次数，修改的时候直接加过去就好了。

这里有一些很好的性质：我们每次用来连接的都是并查集的根，而一个根连到另一个根之后，这个值本身就消失了。而且我们在这里并不用这个并查集查询。因此这里的并查集并不会进行路径压缩，是 $O(1)$ 的。

然后如果是查询全局某个数的出现位置，那么直接 $O(1)$ 查询即可。

我们考虑查询所有位置的实际值。这里就需要用到并查集的找父亲的操作了。由于这里访问了并查集的所有位置，并进行了路径压缩，所以总复杂度是 $O(n)$ 的。

到这里，接下来的步骤就非常明显了。我们对序列进行分块。

对于一个块的全局修改、全局查询，我们直接按照上述方式去做即可，总时间复杂度 $O(n\sqrt n)$。

对于一个块的部分修改，我们先暴力把每个位置的实际值还原，然后对块进行重构即可。单次 $O(\sqrt n)$。

对于一个块的部分查询，我们直接使用并查集找到每个位置的实际值，然后判断是否相等即可。单次不超过 $O(\sqrt n)$。

总时间复杂度 $O(n\sqrt n)$。

我们来分析空间复杂度。我们需要对每个块记录每个数的出现次数，那么至少需要一个 $O(n\sqrt n)$ 的数组。这非常不可接受。

不过我们可以发现，我们在分块的时候，块是独立的，块与块之间不会相互影响。所以我们可以将操作离线，对每个块都按顺序处理一遍所有的操作，然后把询问的答案累加即可。

这样我们只需要开一个块需要使用的空间，然后共用这些空间即可。

所以空间复杂度 $O(n)$。