莫队
莫队的运用非常广泛，今天我们就主要收录莫队的常见运用，以及一些思维和实践上的小技巧。
基础莫队
众所周知莫队是一种离线算法，而这里的基础莫队，指的是多关键字的莫队。
基础莫队要求支持计算单个元素变化的贡献，并且与元素贡献的顺序无关。
当我们的询问有多个关键字时，我们可以无脑地考虑莫队。（有修改的情况可以视为增加了“时间”这一关键字）
如果我们能够以\(O(k)\)的时间复杂度处理每一维增加或者删除一个元素（其实后面我们可以知道只需要处理增加即可），那么整体的复杂度就可以很优秀的变为\(O(n^{\frac{m*2-1}{m}}*k)\)，其中\(m\)是关键字的个数。
它的核心思想是分块，块的大小的取值可以使用均值不等式计算：
\[Time=q*s*m+\frac{n^m}{s^{m-1}} \]当\(s\) 取值近似\(\sqrt[m]{n^m*q}\) 的时候，时间复杂度较优。
回滚莫队
针对基础莫队中，删除操作不好进行的一些问题，可以使用回滚莫队（比如并查集）
回滚莫队要求支持撤销。
回滚的过程很简单，对于在一个小块内的询问，直接暴力计算。
否则，对于每个左端点同块，右端点递增的查询，右端点扩展信息保留不变，每次从块的右边界向左拓展左端点，计算完答案之后进行回溯。
可以证明，对于任意维度的基础莫队，回滚的时间复杂度不变。
离线莫队
针对基础莫队中，单次修改操作时间复杂度为\(O(k)\)，开销过大时，可以使用二次离线莫队。
二次离线莫队要求支持将询问操作进行前缀转化（比较经典的就是区间逆序对问题）。
我们记原序列中每个元素对区间\([l,r]\)的贡献为\(f(x,l,r)\)，那么我们的答案可以如下表示：
\[ans(l,r)=\sum_{x=l+1}^{r}f(x,l,x-1) \]其实就相当于我们做莫队，但是每次都是从左到右完全扫描整个区间，依次更新答案。
对上述式子我们可以进行差分：
\[f(x,l,x-1)=f(x,1,x-1)-f(x,1,l-1) \]显然，这个式子前面那部分，我们阔以直接算，从\(1\) 到 \(n\)跑一遍，每次\(O(k)\)计算，就算好了。
而后面那一部分，怎么看都不像很好看的样子。
所以我们可以尝试转换，将“贡献”转化为“影响”，令\(g(i,x)\)表示\([1,i]\) 对 \(x\) 的影响。
那么原式就可以转化为：
\[ans(l,r)=\sum_{x=l+1}^{r}{g(x-1,x)+g(l-1,x)} \]可以发现这么一来，我们要计算的东西就变成了两个前缀，分别是关于\(x-1\)和关于\(l-1\)的，然后要查询的\(x\)也是连续的一段区间，可以直接对每个前缀开个\(vectoir\)存一下查询的\(x\)（或区间）。
可是这么暴力计算的时间复杂度还是很高啊。那么我们可以考虑不直接结算这个询问的答案，而是结算每个询问的增量，显然这个增量可以用莫队优化为 \(n*\sqrt{n}\) 的级别，于是所有问题都成功解决了。
树上莫队
对于树上的链查询问题，我们可以用括号序拍平成区间上的问题，然后套用莫队解决。
这里提供一个小\(Trick\)，可以避免分讨：对于查询的 \(u\) 是 \(v\) 的父亲的情况，不需要额外分讨论，只需要在记录区间的时候记录为\([dfn_u+1,dfn_v]\) 即可，然后按照折链的方法计算（折链在最后会算上一个算漏的\(lca\)的贡献）
并行莫队
其实本来没有这么一个东西，但是为了好玩我就随便给它取了个名字。
我们发现，你查询的数量级总共才\(O(q)\)，但是你修改的数量级很大，如果你发现单次修改的时间复杂度比较高，可以考虑提升单次查询的时间复杂度，比如使用值域分块，可以做到 \(O(1)\) 修改 \(O(\sqrt{n})\) 查询，比\(O(log)\) 修改 \(O(log)\) 查询优秀很多。
这个东西没有特定的套路或者模板，但是绝大多数的题都是结合了根号算法和数据结构来实现，核心思想都是平均修改和查询的复杂度，故称作并行莫队。
小Tricks
-
关于时间复杂度
对于某些不得不使时间复杂度变为\(O(n*\sqrt{n}*log)\)的问题，我们可以改块长为\(\sqrt{n*log}\)来使得最终的时间复杂度为\(O(n*\sqrt{n*log})\)。
-
关于基础莫队
有的题目有要求删除不能空删，这个时候应该先添加，后删除。
-
关于莫队作用
莫队维护的并非一定是区间的答案，而是关于关键字的答案，比如维护两个前缀和互相的贡献之类的。
-
关于莫队优化
有一个神奇的莫队优化：奇偶排序，偶块第二关键字从大到小排序，奇块第二关键字从小到大排序，相传可以优化近\(O(\frac{1}{3})\)的常数。