基于分块优化的暴力。
离线算法，适用于能够快速加减单点的贡献的区间询问。
普通莫队
板子题：P1494 「国家集训队」小Z的袜子 或者：P2709 小B的询问。
给出长为 \(n\) 的序列 \(a\)，每次询问区间内 \(\displaystyle \sum_{i=l}^r a_i^2\)。
从暴力开始优化：
一个区间询问可以移动左右端点来得到另一个区间询问的答案，从而避免重复计算两个区间重叠的部分，那就设两个指针 \(l,r\)，在序列上移动。
但还是会被卡成 \(\mathcal O(n^2)\)。
于是将询问 \([l,r]\) 离线下来排序，怎么排？
将序列分块，\(l\) 所在块相同就按右端点排，不同就按 \(l\) 所在块排。
复杂度
对于 \(l\)，每个块内有 \(k_i\) 个询问，块内最坏 \(\mathcal O(k_i\sqrt{n})\)，总共 \(\mathcal O(\sum k_i\sqrt{n})=\mathcal O(n\sqrt{n})\)。
对于 \(r\)，每个块最坏移动 \(n\) 次，总共 \(\mathcal O(n\sqrt{n})\)。
不考虑计算答案复杂度，这样莫队的总体复杂度就是 \(\mathcal O(n\sqrt{n})\)。
奇偶性优化
为了衔接相邻两个块的 \(r\) 指针，\(l\) 所在块为奇数就令 \(r\) 升序，偶数则降序。
树上莫队
SP10707 COT2 - Count on a tree II
给定 \(n\) 个结点的树，每个结点有一种颜色，\(m\) 次询问，每次询问 \(u,v\) 之间的路径上的结点的不同颜色数。
\(1\le n\le 4\times 10^4\)，\(1\le m\le 10^5\)。
把树转化成括号序，就是序列问题了，设 \(st_u,ed_u\) 表示欧拉序中 \(u\) 的进栈、出栈顺序。
\(st_u<st_v\) 时：
- \(u\) 为 \(v\) 的祖先，查询 \([st_u,st_v]\) 中所有出现 \(1\) 次的点的答案；
- 否则，查询 \([ed_u,st_v]\) 的所有出现 \(1\) 次的点的答案，记得单独处理 \(\operatorname{LCA}\)。
通过重链剖分可以轻松得到 \(\operatorname{LCA}\) 和括号序，然后就是普通莫队问题了。
带修莫队
相对于普通莫队多了修改操作。
同样是把左右操作离线，分开询问和修改，并都打上时间戳。
可以想到多设一个指针在 \(p\) 在修改操作的序列上移动，对于莫队过程中相邻的两个询问的时间戳 \(t_x,t_y\)，将 \(t_x,t_y\) 之间在当前区间内的修改操作统计到答案里。
发现这样单次会被卡成 \(\mathcal O(n)\)，怎么优化？
调整排序方法
- 第一关键字：\(l\) 所在块；
- 第二关键字：\(r\) 所在块；
- 第三关键字：时间戳。
这样 \(l\) 所在块相同并且 \(r\) 所在块相同的若干个询问，会按照时间总小到大排序。
调整块的大小
设修改操作序列长为 \(t\)，将块的大小调整为 \(\sqrt[3]{nt}\) 最优，此时总体复杂度 \(\mathcal O(\sqrt[3]{n^4t})\)。
证明见 Minclxc 的博客。
懒得话实测 \(n^{\frac{2}{3}}\) 跑的更快，毕竟 \(n\)，\(t\) 同阶。
回滚莫队
给出长为 \(n\) 的序列 \(a\)，\(c(x)\) 为 \([l,r]\) 中 \(x\) 出现的次数，每次询问区间内 \(\displaystyle \max_{i=l}^r \{a_i\times c(a_i)\}\)。
发现由于 \(\max\) 的性质，莫队无法做到 \(\mathcal O(1)\) 减去某个点的贡献。
只能加点不能删点，这时候回滚莫队就出现了。
还是先套路地分块，像普通莫队一样排序（不加奇偶性优化）。
同一个块里的询问右端点单调递增，满足只加不减。
发现左端点在块里反复横跳，干脆每次都从块的右端向左扩展，这样总复杂度仍然控制在 \(\mathcal O(n\sqrt{n})\)。
好了，现在有了完整的思路：
为了方便，将询问按左端点所在块分组，组内排序。
注意要将左右端点在同一块的询问单独处理。
对于每一个块内，设指针 \(l,r\)，我们要保留块的右端点到上一次 \(r\) 的答案为 \(last\) ；
\(r\) 从上一次的 \(r\) 向右扩展，更新 \(last\)；
\(l\) 从块的右端暴力向左扩展，更新答案后撤销掉贡献的所有 \(c(a_i)\)。
二次离线莫队
给了你一个序列 \(a\)，每次查询给一个区间 \([l,r]\) 查询 \(l \leq i< j \leq r\) 且 \(a_i \oplus a_j\) 的二进制表示下有 \(k\) 个 \(1\) 的二元组 \((i,j)\) 的个数。
\(1 \leq n , m \leq 100000 , 0 \leq a_i , k < 16384\)。
莫队需要考虑怎么从 \([l,r]\) 的答案 \(\mathcal O(1)\) 得到 \([l-1,r],[l+1,r],[l,r-1],[l,r+1]\) 的答案。
设 \(f(x,[l,r])\) 表示 \(x\) 对区间 \([l,r]\) 的贡献，每次增减的答案就是这个东西，但是很难计算。
考虑差分，以从 \([l,r]\) 扩展到 \([l,r+1]\) 为例： \[ f(r+1,[l,r]) = f(r+1,[1,r])-f(r+1,[1,l-1]) \] 发现 \(f(r+1,[1,r])\) 可以预处理出来，重点是后面的这项，莫队的过程中在线的求很难。
所以就把对 \(f(r+1,[1,l-1])\) 的询问再次离线下来（这也就是叫做“二次离线”的原因），把 \(r+1\) 挂在 \(l-1\) 的 vector 上，莫队之后从前到后扫，就类似扫描线一样处理。
其它的三种情况类似。
具体的预处理方法，运用异或运算的性质：\(a \operatorname{xor} b=c \Leftrightarrow a \operatorname{xor} c=b\)，所以处理 \(\binom{14}{k}\) 个可能的结果，开个桶统计即可。
并且每次将 \([l,r]\) 扩展到 \([l,r']\) 时，中间需要挂在 \(l-1\) 处的点是个区间，可以将空间复杂度由 \(\mathcal O(n\sqrt{n})\) 降到 \(\mathcal O(n)\)。
这题有个坑点：\(k=0\) 时，在差分处理 \(f(x,[l,r]),x\le r\) 时，\(x\) 在桶中会多算一次，因为 \(x\operatorname{xor}x=0\) 但不符合题目要求。
总结一下，二次离线就是在莫队时，通过扫描线一类的方法，将需要更新的答案再次离线处理。
一些题目
-
树上莫队 + 带修莫队。
二合一，没啥，就是不太好码。
咕~