莫队学习笔记（1）普通莫队
莫队算法（Mo's Algorithm）实质上是暴力的优化，在离线情况下利用分块思想和增量思想来处理区间询问问题。
考虑一个非常简单的问题：给定长为 $n$ 的序列，$q$ 次询问，每次询问 $[l,r]$ 的和。
虽然这个问题有很多更优秀的做法（如前缀和与差分等）处理，但是假设询问的不是区间和而是一些非常复杂的信息导致这些做法都无能为力时，我们就需要考虑如何优化严格 $O(nq)$ 的直接暴力。
考虑对暴力进行一个小小的优化，若我们维护当前询问区间的答案，处理下一个询问时将左右端点移动到该询问区间的位置，在这一过程中不断在左右端点处插入或删除一个位置来更新答案。
这样的话并不是严格的 $O(nq)$，若相邻两个询问区间的左端点之间的距离和右端点之间的距离都很小时非常优秀，但如果很大仍然会被卡成 $O(nq)$，因为我们的左右端点可能会移动很远才能到达下一个区间的位置，那么我们能否优化一下来减少移动距离呢？
考虑将所有询问离线下来并分块，以左端点所在的块为第一关键字，以右端点所在的位置为第二关键字从小到大排序。
这样复杂度会优化到什么程度呢？不妨设块长为 $B$，则一共有 $\lceil\dfrac{n}{B}\rceil$ 个块。
对于块内，虽然左端点是乱序的但是右端点是单调不降的，所以左端点的移动为 $O(Bq)$，右端点的移动为 $O(\dfrac{n}{B}n)=O(\dfrac{n^2}{B})$。
对于块间，由于只有 $\lceil\dfrac{n}{B}\rceil$ 个块，所以左端点的移动为 $O(\dfrac{n}{B}B)=O(n)$，右端点的移动为 $O(\dfrac{n}{B}n)=O(\dfrac{n^2}{B})$。
因此总时间复杂度为 $O(Bq+\dfrac{n^2}{B})$，显然取 $B=\lceil\dfrac{n}{\sqrt{q}}\rceil$ 时最优，总时间复杂度为 $O(n\sqrt{q})$，就变成了根号科技！
普通莫队的一个常数优化是预处理出每个询问左端点所在的块的编号，而不是在比较函数里面求，这样能大幅度减少除法运算次数。
普通莫队还有一个常数优化，不妨来看下面这个例子（假设块的大小为 $2$，有 $4$ 个询问）。
1 1 2 100000 3 1 4 100000
当第一个块处理完后左端点 $l=2$，右端点 $r=100000$，此时我们显然可以发现如果 $l$ 移到 $4$ 就可以顺便处理第 $4$ 个询问。
但是由于 $r$ 在每个块内都是从小到大排序的，所以是直接将 $r$ 移回 $1$ 处理第 $3$ 个询问，再将 $r$ 移到 $100000$ 处理第 $4$ 个询问。
因此考虑奇偶化排序来优化，奇数块的右端点都从小到大排序，偶数块的右端点都从大到小排序，这样处理完了奇数块 $r$ 就可以直接往左移动顺便处理偶数块，处理完了偶数块 $r$ 就可以直接往右移动顺便处理奇数块，这样能够减少不少 $r$ 不必要的移动。
- 例题 1：P3865 【模板】ST 表
题意：给定长为 $n$ 的序列和 $m$ 次询问，每次询问区间 $[l,r]$ 的最大值，$1\le n\le10^5,\ 1\le m\le 2\times10^6$，时限 $0.8$s。