简介
属于离线算法中的一种。
用来解决离线区间询问问题，
将其加以扩展后，还可以解决树上路径询问问题和支持修改操作。
使用条件
须满足以下条件：
对于区间$[l,r]$，
其查询后的答案，能够在$O(1)$扩展到其相邻区间的答案。
即：
$[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$这四个区间
实现
如果满足使用条件后，
自然而然就能想到这种解题方法：
根据上一个询问，一步步扩展到当前询问。
这就是莫队算法中最基本的解题思路，
这样一直扩展下去，就能得到所有询问的答案。
但如果就按照题中给的询问顺序，一个个挨着扩展的话，
肯定会造成大量的重复移动操作。
e.g.
99 100 1 2 99 100 1 2 99 100每次
l和r都会从一端极值移动到另一端极值。
不排序直接求解，易得其复杂度为$O(n^2)$。
因此莫队算法的核心则是：
我们应该怎样对询问排序，使得这一步步扩展的操作次数尽量少。
也就是该如何定义排序算法。
排序算法
1. 直接排序
首先自然而然想到的排序算法就是：
直接按照询问的l和r为主次关键字进行排序。
结构体的<定义为：
struct queryType_direct
{
int l, r, id;
bool operator<(const queryType_direct &a) const { return l == a.l ? r < a.r : l < a.l; }
//当l不同时，l小的排在前面；
//当l相同时，r小的排在前面。
} direct[MAX_M + 5];
但这样排序算法十分粗糙，
其复杂度仍为$O(n^2)$，仅常数小一些而已，
很容易TLE。
复杂度大致计算方式：
以这种排序方法，
l为升序，所以移动次数最坏为$n$，
r最坏情况为反复在两端点间移动，移动次数为$\frac{(n-2)n}{2}$（等差数列计算）。总移动次数最坏为$\frac{n^2}{2}$，
故复杂度为$O(n^2)$。
2. 分块排序
为最有效又简单的排序算法。
具体方法为：
将$n$个询问分为$M$个块。
对于同一个块，按照r的大小排序，
对于不同的块，则按照l的大小排序。
结构体的<定义为：
int BLOCK_SIZE;
struct queryType_block
{
int l, r, id;
bool operator<(const queryType_block &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? r < a.r : l < a.l; }
//当 l/BLOCK_SIZE == r/BLOCK_SIZE 时，为同一块，按照r的大小排序；
//不为同一块时，按照l的大小排序。
} block[MAX_M + 5];
而块的大小BLOCK_SIZE，一般取为$\sqrt{n}$。
虽然看起来很粗糙，与直接排序的区别十分小（就多了个/BLOCK_SIZE），
但其复杂度却能显著的降到$O(n\sqrt{n})$。
复杂度计算方式：
OI-Wiki上的证明方法太多了懒得看x，这里用另一种很不严谨的方式来说明orz……
同一块中，询问个数和块的长度均为$\sqrt{n}$，
l最坏情况也为反复在两极值端点间振荡，但端点距离变为了$\sqrt{n}$，移动次数大致为$\sqrt{n}*\sqrt{n}=n$，
r为递增，所以最坏情况移动次数为$n$，跨块的时候，
l最坏移动$\sqrt{n}$次，
r最坏移动$n$次，所以每一块（同时算上同一块和跨块的移动操作）移动次数大致为$3n+\sqrt{n}$，
一共$\sqrt{n}$块，
故最坏情况，总移动次数为$3n\sqrt{n}+n$。即复杂度为$O(n\sqrt{n})$。
2.(1). 分块的优化——奇偶化排序
对于这组已排好序的数据：
（令：n为100，即BLOCK_SIZE为$10$）
1 1 2 100 10 11 11 100
如果就按照这样的顺序进行操作，
在第二步r为$100$后，
执行第三步会跳到$11$，执行第四步又会跳到$100$。
而将顺序改为：
1 1 2 100 11 100 10 3
则能减少从一极值跳到另一极值的情况。
也就是说，对于第二种“分块排序”方法：
在执行完某一块跳到下一块的时候，
r会从当前块的最大值，唐突移动到下一块的最小值，
从则造成多余的移动操作。
而如果将奇数块改为从小到大排序，偶数块改为从大到小排序，
则在跳块的时候，能很平滑的从这一块最大过渡到下一块最大。
这种优化能使程序快$30%$。
结构体的<定义为：
int BLOCK_SIZE;
struct queryType_block_pro
{
int l, r, id;
bool operator<(const queryType_block_pro &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? (r == a.r ? 0 : (l / BLOCK_SIZE & 1) ^ (r < a.r)) : l < a.l; }
//这里运用位运算，实现了当为奇数块时从小到大排序，偶数块时从大到小排序。
} block_pro[MAX_M + 5];
注意：需要特判r == a.r的情况！
否则对于两询问$a,b$，
其l属于同一奇数块，且r相等的情况，
排序时会同时满足$a<b$和$b<a$，
使得sort()出错。
sort出错原因是因为其要满足严格弱序，
有关严格弱序的介绍可以看这里写的「ACM学习笔记：邻项比较排序……」文章中有提及。
理解不了压行写法的话，也可以看OI-Wiki上的不压行写法。
3*. 曼哈顿最小生成树排序
其实最优的排序方法，是构造曼哈顿最小生成树。
一种方法是把所有区间$[l,r]$看成平面上的点$(l,r)$，并对所有点建立曼哈顿最小生成树，
每次沿着曼哈顿最小生成树的边在询问之间转移答案。
引自：OI-Wiki。
但其复杂度其实也是$O(n\sqrt{n})$，
故一般都采用最简单的分块排序。
【个人也完全不会这个排序方法就不写了_(:з」∠)_……
操作次数比较
以莫队模板题“P1494 小Z的袜子”来进行比较。
当$n,m$较大时：
- “Raw”：未排序直接操作。
- “Direct”：直接排序。
- “Block”：分块排序。
- “Block Pro”：分块排序+奇偶化。
但注意：
分块排序的操作次数不一定恒小于直接排序。
当$n,m$较小时，很有可能反而大于直接排序。
可以发现反而直接排序操作次数更少。
但由于当$n,m$较大时，这种情况几乎不存在，
所以可以不用考虑。
注意事项
排完序后，会破坏原有询问的顺序，
故要加个id变量，来存储原询问的顺序。
移动操作
当排好序过后，关键就是：
如何通过现在求得的$(l,r)$区间的答案$ans$，
一步步移动l和r，
来求得新区间$(l’,r’)$的答案$ans’$。
需要先根据题目分析，
来计算出增加或删除某个元素，对答案的影响。
然后用while判断，一步步l++、l--、r++、r--，
得到新询问区间的答案。
while的位置很重要，不能随意调换他们的位置。
可以简单记住以下三种正确顺序：
l--, r--, r++, l++l--, r++, l++, r--l--, r++, r--, l++
【l--和--l一样，只要l的加减与r的加减顺序对了就行。
有关证明，可见OI-Wiki上的「关于四个循环位置的讨论」。
总模板
int BLOCK_SIZE;
struct queryType
{
int l, r, id;
bool operator<(const queryType_block_pro &a) const { return l / BLOCK_SIZE == a.l / BLOCK_SIZE ? (r == a.r ? 0 : (l / BLOCK_SIZE & 1) ^ (r < a.r)) : l < a.l; } //分块+奇偶化
} query[MAX_M + 5];
inline void move(int pos, int sign, int &nowAns) //sign=1代表增加，sign=-1代表减少。
{
// update nowAns
}
void solve()
{
BLOCK_SIZE = sqrt(n);
sort(query + 1, query + m + 1);
int nowL = 1, nowR = 0, nowAns = 0;
#define L query[i].l
#define R query[i].r
#define ID query[i].idid
for (int i = 1; i <= m; i++)
{
while (nowL > L)
move(--l, 1, nowAns);
while (nowR < R)
move(r++, 1, nowAns);
while (nowL < L)
move(l++, -1, nowAns);
while (nowR > R)
move(--r, -1, nowAns);
ans[ID] = nowAns;
}
}
例题
- P1494 小Z的袜子
题解可见「ACM练习——P1494 小Z的袜子……」。