第二分块 题解

· · 题解

第二分块。

我们观察一下这个查询操作。把所有大于 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)。