一、普通莫队
莫队是一种基于分块的算法，由莫队提出（orz）。
莫队可以解决一类查询序列区间信息的题。
可以使用该算法的 前提 是维护的信息必须可以在 \(O(1)\)（如果用 map / set 可以带 \(\log\)，或者优化成 \(O(1)\)）内将 \([l, r]\) 的答案扩展到 \([l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]\)。
-
将序列分块，并将所有询问离线。然后将左端点所在的块的编号作为第一关键字，右端点作为第二关键字，将询问排序。
-
记 \(q_i\) 为第 \(i\) 个询问，\(m\) 为询问个数，那么我们暴力的从 \(q_1\) 改到 \(q_2\)，从 \(q_2\) 改到 \(q_3\)，一直改到 \(q_m\)。
-
分析时间复杂度。设块长为 \(L\)，假定扩展区间复杂度为 \(O(1)\)；左端点在一个块内的询问，移动最多 \(n\) 次，有 \(\dfrac{n}{L}\) 块，所以这部分的复杂度为 \(O\left(\dfrac{n^2}{L}\right)\)，因为这样每次改可能跨越块，所以这部分的复杂度为 \(O(mL)\)，总复杂度 \(O\left(\dfrac{n^2}{L} + mL\right)\)。我们要让这个式子尽可能小，所以要让这两项相等，即 \(\dfrac{n^2}{L} = mL\)，解得 \(L = \dfrac{n}{\sqrt{m}}\)，时间复杂度 \(O(n\sqrt{m})\)。