根号分治

· · 算法·理论

简介

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

例题

CF506D Mr. Kitayuta's Colorful Graph

依次考虑每个颜色 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 有关。