根号分治

利用根号平衡的思想对问题进程分治解决。

依次考虑每个颜色 $c$，用并查集合并，我们有两个算法。

算法 1：扫描 $q$ 个询问并更新，单次 $O(q)$。

算法 2：考虑同一颜色的点对，对答案的贡献（可以用 map 存，最后在加到答案），单次 $O(n_c^2)$，其中 $n_c$ 是与颜色 $c$ 边邻接的点数，显然 $n_c \le 2m_c$。

算法 1 不依赖点数，但本身代价比较大，不能执行太多次；而算法 2 在点数少的时候表现比较好。

于是根号分治，在 $m_c < \sqrt{m}$ 时使用算法 1，在 $m_c \ge \sqrt{m}$ 时使用算法 2。

算法 1 部分的最差复杂度为 $O(m\sqrt{m})$。不妨设 $\forall c, m_c < \sqrt{m}$，且 $\sum_c{m_c} = m$，根据均值不等式，$m_1 = m_2 = \dots = \sqrt{m}$ 时，$\sum_c{m_c^2}$ 最大，为 $O(m\sqrt{m})$。

算法 2 部分至多执行 $\frac{m}{\sqrt{m}} = \sqrt{m}$ 词，故这部分复杂度为 $O(q\sqrt{m})$。

总复杂度 $O((q + m)\sqrt{m})$。

这个分析没有考虑 $n$ 的限制（因为麻烦），实际上有更紧的下限跟 $n$ 有关。