P4119 [Ynoi2018] 未来日记 题解

· · 题解

闲话

那么按照 Ynoi 的惯例是题解之前先说一大堆废话对吧。

第六分块可能这辈子都写不出来了，不过最初分块过了，写篇题解纪念一下。

不过最初分块评分比第六分块还高我表示怀疑。

这题其实还算好调啦（想当年我第二分块调了两个月才过。

另外要感谢 @sunset1028 巨佬帮我卡常：Link（这题卡常相当严重哦。

描述

给你一个数列，支持区间替换和区间查询第 k 小，n,m,a_i\le10^5.

题解

先考虑区间查询第 k 小，然而像可持久化线段树或者树套树都没法维护这个修改操作。

考虑分块。那么一般分块求区间第 k 小基本上用的就是像由乃打扑克那样的值域二分然后块内二分的做法对吧。不过这样的复杂度是 O(n\sqrt{n\log n}\log n)，由乃打扑克允许这样的复杂度通过，但是这题不行。

那么我们观察一下这题和由乃打扑克有什么区别。

考虑值域分块。由乃打扑克那题因为值域最高可达 $O(2\times 10^9)$，你要是敢值域分块的话复杂度就是 $O(n\sqrt{2\times 10^9})$，肯定是 TLE 无疑了。不过这题 $a_i\le 10^5$ 就可以值域分块。 令 $b_{i,j}$ 为前 $i$ 个块中值在第 $j$ 个值域块的数的个数，$c_{i,j}$ 为前 $i$ 个块中值恰好等于 $j$ 的数的个数。查询时对零散块的所有值再开个桶，然后值域分块。花费 $O(\sqrt{n})$ 的代价枚举答案在哪个值域块内，再花费 $O(\sqrt{n})$ 的代价枚举答案具体是多少。注意我们这里维护的是前缀和，不然 $O(\sqrt{n})$ 枚举答案时还得把 $\sqrt{n}$ 个块的值挨个加起来，时间复杂度就又变成 $O(n)$ 了。 然后我们来考虑这个修改操作。零散块显然直接重构，整块先把 $b,c$ 数组差分然后直接修改，再做一遍前缀和还原回去，由于这个前缀和长度仅为 $\sqrt{n}$ ，所以暴力重构是正确的。但是零散块查询很麻烦，实现这玩意有两种做法。 - 并查集 利用并查集把块内所以值相同的点放在一起，修改时直接合并并查集，注意只修改并查集祖先的值，零散块查询时找祖先即可，**可以通过一些均摊分析发现这个并查集是 $O(1)$ 的**。 - 分类讨论 1. 块内无 $x$： 跳过，原因显然。 2. 块内有 $x$ 无 $y$： 把 $x$ 映射成 $y$ 即可。 3. 块内有 $x$ 有 $y$： $O(\sqrt{n})$ 重构，因为整个块初始总共至多会出现 $O(\sqrt{n})$ 种不同的数字，修改时至多会给两个零散块增加 $1$ 个数字种数，均摊给 $\sqrt{n}$ 个块就也是 $O(\sqrt{n})$ ，出现这种情况时块内的数字种数会减少 $1$，因此重构的次数不会超过 $O(n+m)$，这部分的时间复杂度也是 $O(n\sqrt{n})$。 **修改时注意特判 $x=y$！！** 然后就做完了，时空复杂度均为 $O(n\sqrt{n})$。 # 代码 代码又臭又长（12.46KB，全谷最长解），还是在参考开头那篇帖子吧。