自动搬运

查看原文

来自洛谷，原作者为

	XZhuRen 骄子风采，青春闪耀

搬运于2025-08-24 23:14:07，当前版本为作者最后更新于2025-04-20 18:44:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

诈骗题。

颜色与颜色的匹配可以 $\mathcal{O}(n)$ 计算，计算一个颜色和其他所有颜色的匹配也是线性的。

考虑暴力把两两答案扫出来，直接用桶记录。

先跑出所有答案。

每次修改即暴力删除修改前有关答案和加入修改后有关答案，记修改前的颜色为 $x$，修改后为 $y$，贡献即修改前删除 $x,y$ 的所有贡献和修改后加入 $x,y$ 的所有贡献。

时间复杂度 $\mathcal{O}(n^2+nq)$。