题解 P5692【[MtOI2019]手牵手走向明天】

· · 题解

P5692 [MtOI2019]手牵手走向明天解题报告：

更好的阅读体验

题意

维护一个长度为 n 的序列，q 次操作，支持区间将颜色 x 变成颜色 y，或者查询区间内 x 与 y 的最近距离。

## 分析 [一年前](https://www.luogu.com.cn/blog/xiaoziyaoxzy/solution-p5397)我在路上做第四分块，折戟沉沙。一年后，我在加强版继续折戟沉沙。 我失败了。我还是以前的那个我。 套路的序列分块。 先考虑怎么查询，每个整块开个二维数组 $dis$ 维护 $a$ 和 $b$ 的最近距离，暴力找散块内部的答案，块间的答案数字一定在第一个/最后一个出现位置，从前往后扫一遍，最后再拼上整块内部的答案。 修改的时候，不难发现除了维护 $dis$ 数组之外的内容都是平凡的。实际上，维护 $dis$ 可以枚举每个既包含 $x$ 又包含 $y$ 的块，对这些块中关于 $x,y$ 的 $dis$ 暴力重构。势能分析一下，若我们将不同块的相同颜色看成不同颜色，那么初始颜色数量为 $n$，每次修改至多增加两个颜色，重构一个块则会减少一个颜色，于是重构次数是线性的。 这样可以做到 $O(n\sqrt n)$ 的时空复杂度。 我们发现 $dis$ 数组的维护比较独立，于是可以离线逐块处理，空间就变成线性了。 ## 代码 咕了。