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

· · 题解

「拭尽破净的第四分块」加强版

首先经典的序列分块，对每个点维护前后面最近的颜色的位置和最近距离，询问时就维护当前颜色最右出现位置就能合并块间贡献。

块内全局修改做法？如果没有 x 就跳过，没有 y 就把 x 变成 y，否则暴力重构，这样每次颜色数 -1，单块只会有 O(\sqrt n) 次，单块时间就是 O(n) 的，空间也是 O(n) 的，此时时空都是 O(n\sqrt n) 的。

接着散块就暴力修改，暴力查询即可，只不过注意到不能每次直接新开颜色，要先继承之前改没的颜色编号。不难发现此时可以逐块处理，空间变 O(n)，时间常数小很多！但是写了第四分块的强制在线后就不想重构代码，所以没写……

注意一些细节：

  1. 整块
    1. 没有出现 x：直接跳过；
    2. 没有出现 y：如果是新颜色，直接 col_{pos_x}\leftarrow y。
    3. 否则 c[pos_{x}]\leftarrow y，计算 y 的新距离，把 x 的编号加入桶，把所有 x 改成 y（这个东西第四分块没必要，但这题要加，不然就会和我一样调大半天）。
  2. 散块
    1. 没有出现过 x 或没有修改 x：直接跳过；
    2. 所有 x 被覆盖：变成整块修改。
    3. 修改部分 x：
  3. 如果修改颜色 x=y 直接跳过，不要修改。（让我调大半天的原因之二）

卡常的话如果你卡过了第四分块，这题也能轻松在 500ms 内过，还是提一句吧，虽然是在第四分块那卡的常就是了：

  1. 经典调块长，我第四分块开 375 最快，这题开 300 最快；
  2. 把记录每块每个颜色离散化的数组 id 的关于颜色的一维放前面，这样内存连续速度会块很多，这很重要，反正加了这个我就从最慢点 700ms 以上变成了最慢点 460 ms；
  3. 记录两个颜色的最短距离的 dis 只用关心 x\le y 的部分，而且 dis 可以优化成二维数组，这样更快。

可能是常数还行，反正我只改了上面三点就卡过了。

恶臭代码