本文介绍莫队算法
引例
现给你一排n个方格，每个方格都有不同的颜色，颜色用1~k进行标号，有两种操作共m个询问：
- 询问从l~r之间有多少不同颜色的方格
- 把x位置的方格改成y颜色
问题分析
首先我们考虑暴力算法
修改颜色操作是O(1)的
而对于每一对给出的l和r，从l~r扫描一遍方格，很容易统计出这个区间内有多少不同颜色，这样的复杂度是O(n)，一共有m个询问，那么总共的复杂度是O(n·m)
但对于较大的数据规模，O(n·m)带来的将会是TLE
于是我们需要寻找一种更加高效的算法
考虑线段树做法
每个线段树节点维护$l_i$~$r_i$的存在颜色数(可以压位做到)，查询区间时采用&运算，更新点时可以应用lazy标记
首先线段树的空间要求很大，在n很大的时候，节点数是很多的，在k很大的时候long long/int64可能满足不了需求(可以用bitset)
线段树做法也有局限性
比较而言，暴力做法的空间要求较小，能否找到一个优化方法使得复杂度降低到可以忍受的程度呢？
莫队算法
莫队算法应运而生
莫队算法是在暴力算法的基础上优化了询问顺序
它本质上也是一个暴力算法
更简单的问题
先考虑之前的问题，如果只有第一种操作(询问l~r颜色数)，应该怎么做
（打表预处理就算了，虽然是静态的数据，不过我猜会爆内存）
分析性质
假如我已经知道[l,r]的答案，那么我可以很快通过转移得到[l,r+1],[l,r-1],[l+1,r],[l-1,r]的答案，这是O(1)的
实现
用一个int数组cnt计数维护当前[l,r]范围内各个颜色的数量
当转移到[l,r+1]的时候，假设r+1位的颜色是color[r+1]，那么当cnt[color[r+1]]==0，说明原来是没有这个颜色的，转移答案+1，最后更新cnt数组，cnt[color[r+1]]++
当转移到[l,r-1]的时候，假设r位的颜色是color[r]，那么当cnt[color[r]]==1，说明r位的颜色是区间内为color[r]颜色的最后一个方块，转移答案-1，更新cnt数组，cnt[color[r]]- -
转移到另外两个区间同理
复杂度
显然，这样的操作：
- 读一个询问
- 转移答案
- 输出
- 循环
复杂度是O(n·m)的
但是考虑到每次询问之间互不影响，那么修改询问顺序也是没有问题的
[$l_i$,$r_i$]->[$l_j$,$r_j$]的代价是$|l_i-l_j|+|r_i-r_j|$
以$\lfloor\frac{L}{S}\rfloor$为第一关键字，$R$为第二关键字对询问区间进行从小到大排序(S为分块块长)
对于每一个询问中的每一个块，横坐标最多变化S，纵坐标最多变化n，所以块与块之间转移复杂度是O(n),总共复杂度是O($\frac{n^2}{S}+mS+\frac{n^2}{S}$)
为了让复杂度最优
对S做偏导
$\partial_S{(\frac{n^2}{S}+mS+\frac{n^2}{S})}=m-\frac{2n^2}{S^2}=0$
解得
$S=n\cdot\sqrt[]{\frac{2}{m}}$
此时的复杂度是最小的，为O($n\cdot\sqrt[]{2m}$) (其实有个$\sqrt2$的常数)
这就是莫队真正work的地方，仅仅修改了询问顺序，就达到了降低复杂度的目标,但也使得它仅仅适合解决离线查找询问问题
更深层次的问题
我们解决了只有查询的问题，开篇的问题还有修改的操作
这个时候就需要修改一下莫队算法，使得它适合解决这一类问题
裸莫队算法的缺陷
刚才我们提到，莫队算法是通过修改询问顺序来降低复杂度的，如果有修改原数据的操作，重排会有一些问题，比如，一部分询问必须排在一部分修改之后，一部分询问必须排在一部分修改之前，否则将会导致错误的询问答案
解决方案
但我们排还是要排的，不能不排，不然还是TLE，那么就考虑在修改操作上做手脚
既然询问和修改得有先后顺序，那么我在原来的询问基础上加一维时间维T，这样排完序以后就知道当前的询问是什么时候询问的，前面有哪些修改操作，其次，我们既要能修改原数据，也要能撤销修改
设分块块长为$S_1,S_2$,以$\lfloor\frac{L}{S_1}\rfloor$为第一关键字，$\lfloor\frac{R}{S_2}\rfloor$为第二关键字，$t$为第三关键字从小到大对询问排序(t表示本次询问之前有t次修改操作)
复杂度
同样的，相邻块之间的转移复杂度是O(n)，t最大变化m，L最多变化$S_1$，R最多变化$S_2$，总复杂度是$O(mS_1+mS_2+\frac{2n^2m}{S_1S_2})$
分别对$S_1$和$S_2$做偏导得
$$
\begin{equation}
\left\{
\begin{array}{lr}
m-\frac{2n^2m}{S_1^2S_2}=0, & \\
m-\frac{2n^2m}{S_1S_2^2}=0, &
\end{array}
\right.
\end{equation}
$$
解得
$S_1=S_2=\sqrt[3]{2n^2}$
此时的复杂度最小 为$O(m\cdot\sqrt[3]{n^2})$
总结
莫队算法本质是一个暴力算法，它通过分块改变询问顺序来降低复杂度，适用于解决一类离线查找询问问题