自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:16:35，当前版本为作者最后更新于2020-01-31 23:31:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

本来不想发题解的，lxl 让我发那我也就分享一下我的大常数维护方法了。

赛时就写了一部分，赛后又补充了没想到的部分，可能有点不太详细

不懂的地方可以私信问我，但是最好不要想着去哪个地方找我的代码交上去，过不了不要怪我

序列分块。

分块，维护每种数的前缀出现次数，以及每种数的前缀出现次数的平方。

我们需要计算一段区间的每种数的出现次数的平方的和，考虑记录前缀的平方和，使用 $(a-b)^2=a^2-2ab+b^2$ 计算。

维护 $f(i,j)$ 表示 $\sum_x cnt(x,i)\cdot cnt(x,j)$。其中 $cnt(x,k)$ 表示颜色 $x$ 在前 $k$ 个块中的出现次数。

对 $f(i,j)$ 的修改，考虑块 $k$ 处的修改，设这种颜色在前 $i$ 块和前 $j$ 块中的出现次数为 $a,b$，在 块 $k$ 中的出现次数增加了 $x$。

对于 $i\leq k,k\leq j$ 的，他们的变化为 $a(b+x)-ab=ax$。我们对每个左端点为 $i$ 的 $f(i,\texttt*)$ 都记录变化量。

对于 $i<k,j<k$ 的，变化为 $0$。

对于 $k<i,k\leq j$ 的，变化为 $(a+x)(b+x)-ab=ax+bx+x^2$。我们对每个左端点为 $i$ 的 $f(i,\texttt*)$ 都记录变化量 $ax$，对每个右端点为 $i$ 的 $f(\texttt*,i)$ 都记录变化量 $bx+x^2$。

这部分可以使用差分的技巧做到 $O(1)$ 修改 $O(\sqrt n)$ 查询。

那么块 $i$ 与 $j$ 之间的所有数的出现次数的平方和，我们只需要知道前 $i$ 个块的平方和，前 $j$ 个块的平方和，$f(i,j)$ 的值，就可以求得。计算的复杂度为 $O(\sqrt n)$。

关于修改操作，边角暴力，中间的如果只有一个数则 $O(1)$ 修改，这会给这个块产生 $O(1)$ 个额外颜色段，否则 $O(\sqrt n)$ 删除块中的段贡献，总产生的颜色数为 $O(n+m)$。此时更新 $f$ 的复杂度为 $O((n+m)\sqrt n)$。

然后对于一个块，如果只有一种颜色，我们不把他计算到 $f$ 中而是在查询的时候计算这个块的贡献。

那么需要计算进 $f$ 的颜色段个数是 $O(n+m)$，所以每次对颜色段进行重新计算前缀信息，时间复杂度 $O((n+m)\sqrt n)$。

总时间复杂度 $O((n+m)\sqrt n)$，空间复杂度 $O(n \sqrt n)$。