普通莫队算法
2026-08-26
一般形式
普通莫队适用于序列上的区间询问,若从 [l,r] 扩展到 [l±1,r],[l,r±1] 的复杂度为 O(1),处理所有询问复杂度为 O(mn)。
流程
莫队的想法是利用分块处理所有询问,容易发现,如果询问区间的某个端点一直单调,会很容易处理,但是直接排序有不行,考虑将左端点分块。
具体的,我们分成 n 块,将每个询问区间按照先分块编号,后右端点大小排序。
在每一块内部的询问,右端点递增,左端点移动范围 O(n),也就是最多移动 2n 步,右端点走的总数为 O(n) 次。
在两块之间,左端点移动最多 2n 步。
全部加和以后,时间复杂度为 O(mn)。
优化
- 对于每个奇数块,右端点递增排序;对于每个偶数块,右端点递减排序。
