莫队算法

有一个序列，且有一些区间询问，便可以考虑用神奇的莫队算法！

实现

莫队是一种离线算法，用到了分块的思想，将序列分块，设每个块的长度为$S$。在输入所有询问之后，按$(\lfloor\frac{l}{S}\rfloor,r)$二元组从小到大排序，之后按顺序暴力移动左右端点并统计答案。

时间复杂度

设序列的长度为$n$，询问个数为$m$，从$[l,r]$扩展到$[l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1]$的时间复杂度为$O(f(n))$，于是从$(l1, r1)$转移到$(l2, r2)$的时间为$O((|l1 - l2| + |r1 - r2|) * f(n))$对于每一个块中的所有询问，最多使$r$移动$n$，每个询问最多使$l$移动$S$，一共有$\frac{n}{S}$，相邻两个块转移的时间复杂度为$O(n * f(n))$，所以总时间复杂度为$O((\frac{n ^ 2}{S}+mS+\frac{n ^ 2}{S}) * f(n))$，当$n, m$同阶时，使$S = \sqrt{n}$，总时间复杂度即为$O(n\sqrt{n} * f(n))$

模板