题解 P5397 【[Ynoi2018]天降之物】

w33z8kqrqk8zzzx33 · 2020-10-18 14:45:22 · 题解

第一个正宗过的大分块 qwq

lxl 在他的博客里说了存在序列分块方法然后我不会根号分治所以。。。

考虑序列分块，每一块里面维护某个值的第一个出现位置，某一个值的最后一个出现位置，和两个值之间在块内最小距离。

如果直接维护每一个块需要 O(n^2) 个信息，内存炸。注意一个块里面最多有 O(\sqrt n) 个互异值，所以可以对每一个块维护离散化，只需要维护 O(n) 个信息了。

现在询问就可以模拟，考虑怎么修改。如果在一个块想把 x 修改成 y，有三个情况：

• x 不出现，可以跳过；
• y 不出现，可以修改 x 的离散化值，距离信息不需要修改；
• x 和 y 都出现。在这里可以暴力更新影响的距离（最多有 O(\sqrt n) 个），因为每一次暴力更新这个块里互异值数量减一。每一个块封顶暴力修改 O(\sqrt n) 次，对时间复杂度的贡献仅仅是 O(n^{3/2})。

然后就好了么？快乐的提交上去，30 分，都跑不过暴力。

开始卡常。

• 优化 1：优化预处理常数。
• 优化 2：直接用数组，不要用 struct 加大常数。
• 优化 3：减少数组访问次数，查找距离的时候保证第一位小于第二维，不要更新太多次。
• 优化 4：重新排列离散化数组维度。
• 优化 5：瞎调块长，选 250。

然后就终于好了。