自动搬运

查看原文

来自洛谷，原作者为

	w33z8kqrqk8zzzx33 **

搬运于2025-08-24 22:10:22，当前版本为作者最后更新于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。

然后就终于好了。