第二道 Ynoi2018 。
Idea：lxl Solution：lxl Std：lxl Data：lxl
“弑尽破净的第四分块” （妈呀这名字好中二啊（谁叫我要用日本轻小说中的东西命名真是作死））
这题就是我想改一个已有的经典根号形式改出来，然后想了想发现可以做
考虑根号分治
存在序列分块做法
对这题的评价：6/11
题意简述
维护一个长 $n$ 的整数序列 $a$ ， $m$ 个操作，可能是以下两种：
- 给出 $x,y$ 两个正整数，将序列中所有值为 $x$ 的数变为 $y$ ；
- 给出 $x,y$ 两个正整数，查询序列中对于所有 $i,j$ 满足 $a_i=x, a_j=y$ ， $|i-j|$ 的最小值，无解输出
Ikaros。
强制在线， $1\le n,m\le 10^5,0\le a_i,x,y\le 10^5$ 。
主要思路
看到所有操作都只涉及整个序列就感觉应该不是序列分块。
所以考虑根号分治。
设 $x$ 在序列中的个数为 $siz[x]$ 。
称满足 $siz[x] \ge \sqrt{n}$ 的数 $x$ 为大的，否则为小的。
无修做法
把每个数 $i$ 出现的位置按顺序丢到一个数组 $V[i]$ 里。
再预处理每个大的数到所有其他值的答案，显然可以每个大的数 $O(n)$ ，预处理复杂度 $O(n\sqrt{n})$ 。
查询的时候如果 $x$ 与 $y$ 均为小，则可以使用类似归并的方法， $O(\sqrt{n})$ 查询排序后的位置数组得到答案；否则直接 $O(1)$ 取出预处理的答案即可。
所以时间复杂度为 $O(n\sqrt{n} + m\sqrt{n})$ 。
带修做法
假设将所有 $x$ 变为 $y$ 。
由于可以通过一些技巧，使得 $x$ 变为 $y$ 等价于 $y$ 变为 $x$ ，所以不妨先设 $siz[x] \le siz[y]$ 。
假设我们一开始预处理的大的数 $B$ 到任意数 $i$ 的答案为 $ans[B][i]$ 。
如果 $x$ 与 $y$ 均为大，我们可以直接 $O(n)$ 重构 $y$ 到每个数 $i$ 的答案 $ans[y][i]$ 。由于需要满足 $x,y$ 均为大，故这样的重构不会超过 $\sqrt{n}$ 次，总复杂度 $O(n\sqrt{n})$ 。
如果 $x$ 与 $y$ 均为小，并且合并后也为小，我们只需要对于每个大数 $B$ ，使用 $ans[B][x]$ 更新 $ans[B][y]$ ，并将 $ans[B][x]$ 设为 $\inf$ 即可。这样单次复杂度为大数个数，即 $O(\sqrt{n})$ 。若 $x$ 与 $y$ 合并后为大，那么直接如上方 $O(n)$ 重构。易得这样的重构也不会超过 $\sqrt{n}$ 次，所以总复杂度 $O(n\sqrt{n})$ 。
然而 $x$ 为小， $y$ 为大时，仅使用 $ans$ 数组来记录答案不可行。若直接 $O(n)$ 重构，总复杂度上升到 $O(n^2)$ ；若只更新每个大数 $B$ 到 $y$ 的答案 $ans[B][y]$ ，正确性出现问题。
假设将 $x_1, x_2$ （小）分别变为 $y_1, y_2$ （大）。则 $ans[y_1][y_2]$ 记录的是原本的 $y_1$ 到原本的 $y_2, x_2$ 的答案的最小值， $ans[y_2][y_1]$ 记录的是原本的 $y_2$ 到原本的 $y_1, x_1$ 的答案的最小值。若现在 $y_1, y_2$ 的答案实际在原本的 $x_1, x_2$ 之间取得，则无法被更新到。故直接更新正确性错误。
我们对每个大的数 $B$ 都开一个附属集合，表示目前序列的哪些位置原本不是 $B$ 但现在变成了 $B$ ，这些位置就应该是在上方讨论过，未被完全更新的位置。将这些位置按顺序放入数组 $V^\prime[B]$ 中，$|V^\prime[B]|$ 记为 $psz[B]$。
对于 $x$ 为小， $y$ 为大时的修改，仍然对每个大数 $B$ 更新 $ans[B][y]$ ，并将所有 $x$ 出现的位置按顺序加入 $V^\prime[y]$ 中。此时一次的时间复杂度为 $O(\sqrt{n} + psz[y])$ 。故若 $V^\prime[y]$ 在加入 $x$ 的位置后， $psz[y]$ 大小已经比 $\sqrt{n}$ 大，需要像 $x$ 与 $y$ 均为大时一样，直接 $O(n)$ 重构 $ans[y][i]$ 。由于这样的重构次数也不会超过 $\sqrt{n}$ 次，总复杂度也是 $O(n\sqrt{n})$ 。
如上述修改，总复杂度即为 $O(n\sqrt{n} + m\sqrt{n})$ 。
接下来假设查询 $x$ 与 $y$ ，先钦定 $siz[x] \le siz[y]$ 。
如果 $x$ 与 $y$ 均为小，可以通过无修时类似归并的方法， $O(\sqrt{n})$ 做。
如果 $x$ 与 $y$ 均为大，先 $\min(ans[y][x], ans[x][y])$ 得到一个答案，再将两数的附属集合像上面的方法一样归并做，两个答案的最小值就是真正的答案，复杂度也为 $O(\sqrt{n})$ 。
如果 $x$ 为小， $y$ 为大，将 $V[x]$ 和 $V^\prime[y]$ 归并做，再与 $ans[y][x]$ 取最小值即为答案，复杂度仍为 $O(\sqrt{n})$ 。
所以总时间复杂度 $O((n + m)\sqrt{n})$ ，空间复杂度 $O(n\sqrt{n})$ 。
参考代码
然而怎么实现？
由于需要支持在修改中交换 $x, y$ ，需要一个数组 $rn[i]$ 来表示数 $i$ 现在在序列中的真实值。
发现当数 $i$ 为大的时候，存 $V[i]$ 没有用，直接把 $V^\prime[i]$ 存到 $V[i]$ 上去，这样合并两个集合或者附属集合就好写多了。
大数肯定要编个号，注意垃圾回收。然后就是注意 $siz$ 和 $psz$ 的修改不要漏了。
实验证明大数的判定标准定到 $500$ 时跑得最快。加了三行指令集之后，跑到了最优解，纪念一下。
1 |
|
对比一下自己写「Ynoi2018」未来日记时的码风发现变化有点大……