题解：P12262 『STA - R9』交错

· · 题解

诈骗题。

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

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

先跑出所有答案。

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

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