第二道 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」未来日记时的码风发现变化有点大……