Summary

莫队,
一种有趣而优美的暴力.

Links

一道模板题:
[P1494 [国家集训队]小 Z 的袜子](https://www.luogu.org/problemnew/show/P1494), 建议结合题解 ([洛谷 P1494[国家集训队] 小 Z 的袜子](https://www.dengmy.xyz/2019/04/29/solution-p1494-lg/))阅读.

Text

莫队是什么

莫队算法一般用于解决 离线的 多次区间信息统计问题.

首先来看一张图片:

.
莫队算法需要维护两个指针 $L$ 和 $R$, 并统计闭 (当然也可以是开, 看你怎么写) 区间 $[L,R]$ 内的信息. 现在假设 $L$,$R$ 分别在紫色^(当前位置) 位置上, 下一个询问需要统计橙色^(目标位置)内的信息. 于是我们需要将两个指针一步步跳转到目标位置.
为了尽可能减少跳转次数, 减小时间复杂度, 我们需要对询问进行排序 (这就是为什么必须离线).

什么时候可以使用莫队

由之前的简单介绍可以知道, 莫队的使用条件十分苛刻:

1. 必须为离线询问 ;
2. 可以方便的跳转到相邻区间 (譬如现在在区间 $[L,R]$, 则必须可以方便的统计 $[L-1,R]$,$[L+1,R]$,$[L,R-1]$,$[L,R+1]$), 最好是可以实现 $O(1)$ 跳转;
3. 没有修改或者修改比较简单(这个需要带修莫队,DengMY 作为蒟蒻当然不会了, 但是可以参考Reference中的文章).

莫队怎么实现

创建两个指针, 然后按照排好的顺序依次跳转处理询问即可.

显然难点在于如何排序. 莫队的排序一般是

1. 将左端点分块, 每块大小为 $size$;
2. 以 左端点所在的块 (注意, 不是左端点) 为第一关键字升序, 右端点的位置为第二关键字升序排序.

则共有 $n/size$ 个块,$R$ 在每个块内最多跳 $n$ 次,$L$ 总共跳不超过 $m*size$ 次, 所以时间复杂度为 $O(m*size+n^2/size)$, 其中 $n$,$m$ 为同一数量级. 显然当 $size=\sqrt n$ 时, 有最小时间复杂度:$O(n\sqrt n)$.

其中有一个小优化就是 当左端点所在块的编号为奇数时, 右端点以升序排, 否则以降序排 , 实测对于例题的最后一个点(P1494#10, 弹出输入密码取消即可) 最多可以加速一半.

Code(以例题为例):

bool operator<(const aqsk &cpr)
{
    if (q[lft] == q[cpr.lft])
        return q[lft] & 1 ? rgt < cpr.rgt : rgt > cpr.rgt;
    return q[lft] < q[cpr.lft];
}

.

Reference

• https://www.cnblogs.com/Paul-Guderian/p/6933799.html