重拾莫队的一点儿思考

发现在过去一年里好多东西都忘光了，于是全部重来。

对于最简单的一个莫队情景：序列长度为 \(n\)，有 \(q\) 次询问，插入、删除复杂度均为 \(O(1)\)。

我们把询问按照左端点排序，然后分块，每一块内再按照右端点来排序……等一等？

考虑一下两种不同的分块方式。

第一种，把原序列按 \(B\) 分块，再将询问按照左端点所在块进行分块。

此时每一块内右端点移动次数为 \(O(n)\) 级别，右端点总移动次数为 \(O(\frac{n^2}{B})\) 级别；

左端点的总移动次数是 \(O(qB)\) 级别。

总复杂度 \(O(\frac{n^2}{B}+qB)\)，当 \(B\) 取 \(\frac{n}{\sqrt q}\) 时平衡复杂度为 \(O(n\sqrt q)\)。

第二种，把询问按 \(B\) 均匀分块。

此时每一块内右端点移动次数仍为 \(O(n)\) 级别，右端点总移动次数为 \(O(n\frac{q}{B})\) 级别；

左端点的总移动次数是 \(O(nB)\) 级别。

总复杂度 \(O(n\frac{q}{B}+nB)\)，当 \(B\) 取 \(\sqrt q\) 时平衡复杂度为 \(O(n\sqrt q)\)。

也就是说这两种分块方式的最优复杂度都是 \(O(n\sqrt q)\)。有趣的是对于第二种，最优块长与 \(n\) 无关。

不过这些分析也没啥用处，实际做题的时候还是直接硬调吧。