题解 P4119 【[Ynoi2018] 未来日记】

BFqwq · 2021-02-06 19:42:23 · 题解

很久以前写的，突发奇想，来补个题解。

在做这个题之前，建议先写一写第二分块。这边有个双倍经验。这边默认都写过第二分块。

在第二分块中，我们用到了一种将某个块中的某个值整体修改为另一个值。在 lxl 的题解中这一操作有三种解法。这边建议直接用并查集，因为好写，但说实话，确实很慢。

修改时大致方法跟第二分块基本相同，对每个块内每个值开一个并查集，然后合并时直接合并即可。当然也可以用其他的方法，比较随意。

查询就是经典的区间 kth 查询。在序列分块的同时值域分块，然后先求出每个块对应每个值域块内的数的个数前缀和。

令 cnt_{j}/sum_{i,j} 表示散块/前 i 个序列块内值在第 j 个值域块的数的个数，cnt1_j/sum1_{i,j} 表示散块/前 i 个序列快内值为 j 的数的个数。其中 sum 预处理，cnt 每次分别统计。

在每次查询时，我们先扫描散块，统计出 cnt_{j} 和 cnt1_{j} 的值，这部分的复杂度显然是 \operatorname O(\sqrt n) 的。

接着我们从小到大扫描所有值域块。由于有了 sum 和 cnt 数组，所以可以 \operatorname O(1) 求出这个值域块内的数的个数。于是我们可以 \operatorname O(\sqrt n) 找到目标位于哪个值域块内。

然后我们从小到大扫描这个值域块内的所有数。与刚才一样，只不过把 sum/cnt 换成 sum1/cnt1，然后就可以找到对应的数。于是就可以 \operatorname O(\sqrt n) 找到要求的数。