普通莫队
板子题：小B的询问
题解（学习笔记）
复杂度分析：分块之后，左端点按块的序号排序，右端点升序。对于每个块来说，右端点总移动量为 O(n)，而每切换一次询问左端点最多移动 O(B) 次。因此复杂度为 O(Bm+\frac{n^2}{B})，取 B=\frac{n}{\sqrt m} 最优，复杂度是 O(n\sqrt m)。
至于这为什么是最优的移动次数，把所有询问区间 [l,r] 看做二维平面上的点 (l,r)，点 (x,y) 与点 (a,b) 的距离为从区间 [x,y] 转移到 [a,b] 所需的移动次数，即曼哈顿距离 |x-a|+|y-b|。那我们想做的其实就是找一条经过所有点的最短路径。首先根据前文所述，对于任意情况总有一条总长度为 O(n\sqrt m) 的路径。接下来只需证明存在一种情况的最短路径长为 O(n\sqrt m)。考虑把二维平面均分为 m 个 \frac{n}{\sqrt m}\times \frac{n}{\sqrt m} 大小的区域，每个区域内随机一个位置作为询问点。那么任意两点间距离是期望 O(\frac{n}{\sqrt m}) 的，最短路径的期望即为 O(n\sqrt m)，因此得证。
习题：
稍微变一下形就会发现它和小B的询问简直一模一样
可以离线后用线段树做。但如何用莫队解决呢？（默认 n,m,|V| 同阶，|V| 表示值域）
注意到我们实际上要支持 n\sqrt n 次单点修改（挪动区间），回答 n 次区间查询。本着平衡复杂度的思路，我们需要一种手段把单点修改做到 O(1)，区间查询 O(\sqrt n)。不难想到对值域进行分块，维护每个数出现的次数以及每块出现过的不同数的个数。查询时整块整块地跳，直到碰到一个不同数个数小于块大小的块，mex一定在这个块里，暴力扫即可。总时间复杂度仍为 O(n\sqrt n)
莫队套树状数组。仍然沿用mex那题的思路，莫队套值域分块即可，不再赘述
高维莫队
对于 x 维莫队，前 x-1 维按所在块序号排序，第 x 维升序。共有 (\frac{n}{B})^{x-1} 种块的情况，每种情况下右端点最多移动 O(n) 次，每切换一次询问左端点最多移动 O((x-1)B) 次，总复杂度为 (\frac{n}{B})^{x-1}n+(x-1)Bm，简单算一下，取 B=\sqrt[x]{\frac{n^x}{m(x-1)}} 最优。如果把 x-1 看做常数，m,n 同阶那就是经典的 n^{\frac{x-1}{x}}。也正因忽略了一个常数所以高维莫队块长最好还是自己手动二分…啊这也印证了只有一维排序的必要性，因为如果有两维是按照升序排每次切换会被卡到 O(n)。而如果哪一维都按分块来显然不如其中一维排序优。
移动次数的最优性证明同二维莫队。
模板题：数颜色
其实就是普通莫队加上了时间维。即把询问 [l,r] 变为询问 [t,l,r]，t 表示第 t 次询问之后（第 t 个版本）。仍然是挪动区间，由于修改是单点修改，所以通过记录每次修改前该位置上的数是多少做到 O(1) 地从 [t,l,r]->[t±1,l,r]。这样就和普通莫队差不多了，注意块长得取到 O(n^{\frac{2}{3}})，总时间复杂度为 O(n^{\frac{5}{3}})
树上莫队
模板题：COT2 - Count on a tree II
树上的问题自然要转化到序列上做，树上莫队自然要转化成序列上的莫队。借助欧拉序，在树上 dfs 时通过时间戳记录每个结点进栈的时间 st 和出栈的时间 ed 并按时间顺序存到一个数组中。这样就把原本 n 个点的树转化为了 2n 个点的序列，我们需要把询问也转化到序列上。
在挪动区间时，如果当前元素代表的结点是第二次出现，就视为这个结点没有出现过（把它删除而不是添加进去）。换句话说，一个结点在这个区间中进栈了一次又出栈了一次就视为其没出现。这样的话对于询问 x,y（不妨令 st[x]\le st[y]），如果 x 是 y 的祖先，询问 (x,y) 就等价于序列上询问 [st[x].st[y]]；如果 x 不是 y 的祖先，询问 (x,y) 就等价于序列上询问 [ed[x],st[y]]\cup lca(x,y)（可以画图感受一下）。
实际上还可以用树分块搞，那样常数会小很多，但是我不会/kk。
二次离线莫队
假设我们的莫队需要动态维护信息以及动态更新答案才能跑，也就是说有 O(n\sqrt n) 次修改和查询（比如区间逆序对），硬上数据结构（比如树状数组）是没有前途的 O(n\sqrt n\log n)。
首先有一个比较好懂的做法是考虑单次移动的查询是一段区间的形式，把它差分成前缀离线下来，然后用值域分块扫一遍。可惜空间是 n\sqrt m 的，因为总共移动 n\sqrt m 次，每次都会差分出两个询问。
接下来是最神奇的地方，我们可以把这些修改和询问都离线下来，预处理一部分，扫描线一部分来做到 O(n\sqrt n) 时间 O(n) 空间。
考虑我们在做莫队的过程中要把 [l,r] 挪动至 [l,r+k]，令 f(x,[l,r]) 表示 x 对 [l,r] 的贡献，答案会增加 \sum_{i=r+1}^{r+k}f(i,[l,i-1])。差分一下变成 \sum f(i,[1,i-1])-f(i,[1,l-1])。f(i,[1,i-1]) 是一个数对一个相邻前缀的形式，本质只有 O(n) 种，可以预处理并前缀和。剩下的部分是一段区间对一段前缀的贡献，这个可以扫描线。
怎么扫描线？直接暴力扫!!!!!!!!!只是为了省空间才压成区间对前缀的形式/fn
回滚莫队
又称不删除/不插入莫队。
仍然是暴力的思想，对于左端点位于同一块内的，从块的边界暴力加入再暴力撤销。实质上是把较困难的操作用撤销实现了。
例如 WC2022T2 就可以采用链表+不插入莫队做到 O(n\sqrt m)。