【做题记录】Ynoi2018 天降之物

  • \(\text{Ynoi 2018}\) 天降之物

题目:

一个长为 \(n\) 的序列 \(a\)。

需要实现 \(m\) 个操作,操作有两种:

  1. 把序列中所有值为 \(x\) 的数的值变成 \(y\)。

  2. 找出一个位置 \(i\) 满足 \(a_i=x\),找出一个位置 \(j\) 满足 \(a_j=y\),使得 \(|i-j|\) 最小,并输出 \(|i-j|\)。

\(n\le 10^5\)。


题解:

考虑根号分治。

对于阈值 block,设一个数出现次数为 \(cnt_x\),那么对于 \(cnt\) 分为比 block 大、小的情况,称作大数、小数。

对于查询两个小数的情况可以直接线性归并得到结果,单次复杂度 \(O(block)\)。

大小超过 block 直接 \(O(n)\) 扫描,因为大数最多 block 次。

考虑对于大数定义它的附属集合为其合并时用过的小数,保证长度 \(\le\) block,否则直接暴力更新。

考虑修改。

小数小数合并,小数就不管,大数暴力更新。

大数大数合并仍然是暴力更新,因为每个大数最多被合并一次,所以均摊下来仍然是 \(O(\dfrac{n}{block})\)。

大数小数则直接把 \(x\) 并入 \(y\) 的附属集合。\(O(\dfrac{n}{block})\)。

考虑查询。

小数小数则暴力合并。

大数大数考虑将 \(x\) 合并到 \(y\) 和将 \(y\) 合并到 \(x\) 的代价的 min。\(O(block)\)

大数小数暴力归并 \(x,y\) 的附属集合(\(x\) 为小数),再与 \(x\) 并到 \(y\) 的情况取 \(\min\) 。时间复杂度 \(O(block)\) 。

总的时间复杂度 \(O((n+m)\sqrt n)\),空间复杂度 \(O()n\sqrt n\)。

至于 block 不一定是严格的 \(\sqrt n\),取到 650 最好。

目前最优解。

上一篇:【洛谷4117】[Ynoi2018] 五彩斑斓的世界(第二分块)


下一篇:【题解】Luogu P5398 [Ynoi2018]GOSICK