离线算法
莫队
普通莫队
限制：
可离线。
可以 $O(1)$ 扩展区间。
问题形式：长度为 $n$ 的序列，$m$ 次询问区间 $[l,r]$。
如果块长为 $s$，将所有询问区间按照 $l$ 所在块划分组（组内按照 $r$ 从小到大排列）：
对于 $l$ 来说，每次最多移动 $O(s)$，总复杂度 $O(m\cdot s)$。
对于 $r$ 来说，每个块所在组最多移动 $n$ 次，一共有 $n/s$ 个组，总复杂度 $O(n\times \frac{n}{s})$。
解 $ms+\frac{n^2}{s}$ 最低时 $s=\frac{n}{\sqrt{m}}$。
奇偶化排序
为了反制恶臭数据让我们反复横跳，可以将询问编号奇偶处理，奇数的 $r$ 从小到大，偶数的 $r$ 从大到小。
带修莫队
普通莫队是不支持修改的，但我们可以加一维时间，即 $[l,r,time]$。
假设序列长为 $n$，$m$ 次询问，$t$ 次修改：
如果块长为 $s$，左右端点每次移动 $O(s)$，复杂度都为 $O(m\times s)$
总时间为 $t$，复杂度为 $O(t\times (\frac{n}{s})^2)$
解 $2ms+t(\frac{n}{s})^2$ 最小得 $s=\sqrt[3]{\frac{2n^2t}{m}}$。
$n,m,t$ 同数量级时复杂度为 $O(n^{5/3})$。
P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列
树上莫队
可以将树上问题转化为序列问题。
记录一个栈，经过 / 离开每个点时入栈，得到一个长度为 $2n$ 的序列。
如果我们想找从 $x$ 到 $y$ 的序列（默认 $x$ 和 $y$ 并非直接祖先关系），不妨从某个点离开时的序列位置出发，直到在序列上到达另一个点。这时除了 $\text{lca}(x,y)$，路径上的每个点都恰好经过一次，而非路径上的点都会经过两次。
因此记录每个树上的点在序列中的访问次数 $vis[x]=0/1$ 进行增减即可。$\text{lca}(x,y)$ 单独维护。
- 如果 $x,y$ 为直接祖先关系，直接从某个点的出现走到另一个点的出现即可，且不用考虑 $\text{lca}$。
回滚莫队
这是为了处理某些难以增加或删除的问题。只需要在普通莫队的基础上，记录当前右端点到左端点所在块之前的状态，每次由此扩展即可。
P14420 [JOISC 2014] 历史的研究 / Historical Research
二维莫队
同一维莫队相似，按照 $x_1,x_2,y_1,y_2$ 关键字排序。
对于 $x_1,x_2$，枚举总复杂度为 $O(q\times s)$。
对于 $y_1,y_2$，先要 $O((\frac{n}{s})^2\times \frac{n}{s})$ 确定 $x_1,x_2$ 所在块，再 $O(n)$ 确定 $y_1,y_2$ 位置，总复杂度为 $O(\frac{n^4}{s^3})$。
解得最小时 $s=n\times q^{1/4}$。