总结 莫队

基于分块优化的暴力。

离线算法，适用于能够快速加减单点的贡献的区间询问。

普通莫队

板子题：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$。

把树转化成括号序，就是序列问题了，设 $s{t}_u,e{d}_u$ 表示欧拉序中 $u$ 的进栈、出栈顺序。

$s{t}_u<s{t}_v$ 时：

• $u$ 为 $v$ 的祖先，查询 $[s{t}_u,s{t}_v]$ 中所有出现 $1$ 次的点的答案；
• 否则，查询 $[e{d}_u,s{t}_v]$ 的所有出现 $1$ 次的点的答案，记得单独处理 $\mathrm{LCA}$。

通过重链剖分可以轻松得到 $\mathrm{LCA}$ 和括号序，然后就是普通莫队问题了。

code

带修莫队

P1903 「国家集训队」数颜色 / 维护队列

相对于普通莫队多了修改操作。

同样是把左右操作离线，分开询问和修改，并都打上时间戳。

可以想到多设一个指针在 $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^{4}t})$。

证明见 Minclxc 的博客。

懒得话实测 $n^{\frac{2}{3}}$ 跑的更快，毕竟 $n$，$t$ 同阶。

code

回滚莫队

AT1219 歴史の研究

给出长为 $n$ 的序列 $a$，$c(x)$ 为 $[l,r]$ 中 $x$ 出现的次数，每次询问区间内 ${\displaystyle \underset{i=l}{\overset{r}{max}}\{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)$。

code

二次离线莫队

P4887 【模板】莫队二次离线（第十四分块(前体)）

给了你一个序列 $a$，每次查询给一个区间 $[l,r]$ 查询 $l\le i<j\le r$ 且 $a_i\oplus a_j$ 的二进制表示下有 $k$ 个 $1$ 的二元组 $(i,j)$ 的个数。

$1\le n,m\le 100000,0\le 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\mathrm{xor}b=c\iff a\mathrm{xor}c=b$，所以处理 $(\genfrac{}{}{0ex}{}{14}{k})$ 个可能的结果，开个桶统计即可。

并且每次将 $[l,r]$ 扩展到 $[l,r^{\prime }]$ 时，中间需要挂在 $l-1$ 处的点是个区间，可以将空间复杂度由 $\mathcal{O}(n\sqrt{n})$ 降到 $\mathcal{O}(n)$。

这题有个坑点：$k=0$ 时，在差分处理 $f(x,[l,r]),x\le r$ 时，$x$ 在桶中会多算一次，因为 $x\mathrm{xor}x=0$ 但不符合题目要求。

总结一下，二次离线就是在莫队时，通过扫描线一类的方法，将需要更新的答案再次离线处理。

code

一些题目

• P4074 「WC2013」糖果公园

  树上莫队 + 带修莫队。

  二合一，没啥，就是不太好码。

  code

• 咕~