Ynoi 大分块系列

最初分块

先考虑怎么用分块维护区间第 \(k\) 小。

首先肯定想到二分区间第 \(k\) 小，然后查询区间有多少个数小于等于 \(x\)。

但这样时间复杂度是 \(\operatorname{O}(n\sqrt{n}\log^2 n)\) 的，无法通过此题。

考虑这样一个事情，我们可以暴力枚举区间第 \(k\) 小，然后查询区间内有多少个数小于 \(x\)，但这样复杂度更高。

不如先将查询区间有多少个数小于 \(x\) 的复杂度降到 \(\sqrt{n}\)，直接对于每个块内的数再次进行值域分块，然后对值域分块的信息做一遍前缀和。
这样子对于整块就可以 \(\operatorname{O}(1)\) 查询，然后对于散块暴力统计，时间复杂度 \(\operatorname{O}(n\sqrt{n})\)。

然后值域分块之后就可以先枚举答案在那个块内，再在那个块内枚举具体是那个数即可。

然后考虑修改。

不难发现，可以用一个类似并查集的东西记录每个数当前被并到了那个数，查询散块的时候直接把每个数找到其所并到的那个数，然后统计。

由于修改时不是整体修改，所以需要对每个块单独维护一个并查集。

为了方便并查集的维护，可以把每个块内一个值的并查集的根设为该数在该块内出现的第一个位置。

在合并值域 \(x\)，\(y\) 时，如果 \(y\) 不存在就直接把 \(y\) 的根改成 \(x\) 的根，否则直接把 \(x\) 的根改成 \(y\) 的根即可。

注意，因为值域分块做了前缀和，所以要记录前缀代价，然后对每个块进行操作。

code