- \(\text{Ynoi 2018}\) 天降之物
题目:
一个长为 \(n\) 的序列 \(a\)。
需要实现 \(m\) 个操作,操作有两种:
-
把序列中所有值为 \(x\) 的数的值变成 \(y\)。
-
找出一个位置 \(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 最好。
目前最优解。