本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-12 18:11:47

本来想放到数据结构那篇里的，但那篇已经很长了，且感觉莫队不太数据结构，故新开一篇记录。

普通莫队：P1494 小 Z 的袜子

莫队思想为将序列以 $B$ 为块长分块，将所有询问离线下来，以 $l$ 所在块为第一关键字，$r$ 为第二关键字排序，然后依次处理所有询问，维护当前区间的 $(L,R)$，每次暴力移动到目标区间即可。注意移动时要先拓展后收缩，否则会在 $L>R$ 时出现错误。

计算一下移动次数，由于左端点单次移动距离是 $O(B)$ 的，右端点在每个块内会移动 $O(n)$ 距离，因此总移动次数为 $O(qB+n+\frac{n^2}B)$，在 $B=\frac n{\sqrt q}$ 时最优，然而一般直接用 $B=\sqrt n$ 就足够了，复杂度不超过 $O((n+q)\sqrt n)$。之后复杂度分析均使用理论最优块长。

本题中求区间 $\sum \frac{t_i(t_i-1)}2$，其中 $t_i$ 为 $i$ 在该区间内出现次数。这里暴力维护桶，每次修改桶时也修改目前答案即可，修改是 $O(1)$ 的，可以使用莫队。另有奇偶优化，即第奇数个块内按 $r$ 从小到大排序，第偶数个块内按 $r$ 从大到小排序，可以减少块间 $r$ 的移动，常数较小。时间复杂度 $O(n\sqrt q)$，提交记录，不带奇偶排序的。

ABC405G Range Shuffle Query

求区间 $[l,r]$ 内小于 $x$ 的数的多重集排列 $\frac {(\sum_{i<x} t_i)!}{\prod_{i<x} t_i!}$，其中 $t_i$ 为 $i$ 在该区间内出现次数。直接离线下来使用莫队，考虑如何处理修改。可以直接使用线段树或树状数组维护两个前缀内容，时间复杂度 $O(n\sqrt q\log n)$，难以通过。考虑换用修改 $O(1)$ 查询 $O(\sqrt n)$ 的值域分块，这样总复杂度降为 $O(n\sqrt q+q\sqrt n)$，可以通过，提交记录。因此有时可以用值域分块平衡来降低莫队复杂度。

带修莫队：P1903 数颜色 / 维护队列

维护序列，支持单点修改，求区间不同数的个数。由于带上了修改，普通莫队无法解决。考虑多记一维 $t$ 表示该询问在 $t$ 次修改之后，同样以 $B$ 为块长分块，以 $l$ 所在块、$r$ 所在块、$t$ 依次为关键字排序，通过暴力移动 $(L,R,T)$ 依次回答询问，所有修改均容易做到 $O(1)$。

计算一下移动次数，设 $c,q$ 分别为修改和查询次数，每个 $l,r$ 块内 $T$ 的变化量不超过 $O(c)$，共 $O(\frac{n^2c}{B^2})$；$L$ 的移动次数为 $O(qB+n)$，分别为块内移动和块间移动；$R$ 在 $l,r$ 块内移动 $O(qB)$，块间移动 $O(\frac{n^2}B)$，$l$ 块间移动同样是 $O(\frac {n^2}B)$。因此总次数为 $O(\frac {n^2c}{B^2}+qB+\frac{n^2}B)$。

最优的 $B$ 不知道，事实上 Deepseek 也没求出来。若假设 $c>B$ 则前两项平衡可得 $B=n^{\frac23}c^{\frac13}q^{-\frac13}$，此时复杂度为 $O(n^{\frac23}c^{\frac 13}q^{\frac 23}+n^{\frac 43}c^{-\frac13}q^{\frac 13})$，不超过 $V^{\frac 53}$。然而在 $c=0$ 时会求出 $B=1$ 导致超时，用 $c+1$ 求块长即可通过。事实上由于块间移动比块内移动更容易跑满，使用 $B=n^{\frac23}$ 时复杂度为 $O(mn^{\frac23}+n^{\frac43})$，且前一项跑不满，可以通过且用时较短。

回滚莫队：AT_joisc2014_c 歴史の研究

求区间 $it_i$ 的最大值，其中 $t_i$ 为 $i$ 在该区间内出现次数。注意到若所有 $t$ 只增不减，则容易维护当前答案，只需要在增加时尝试更新即可。然而莫队区间收缩时会使得 $t_i$ 变小，难以维护答案，需要使用回滚莫队。

具体地，若询问在某块内则暴力计算答案。将剩余询问放到 $l$ 所在块上，将同块询问按 $r$ 排序后统一处理。同样维护 $L,R$，初始时 $R$ 为 $l$ 所在块右端点，$L=R+1$。之后每到一个询问先暴力将 $R$ 向右拓展，由于已排序，$R$ 单调不降，然后记录目前答案 $X$ 以供回滚。再将 $L$ 向左拓展并记录答案，之后将 $L$ 回滚到初始状态，并把目前答案回滚为 $X$ 即可。这样每个块内 $R$ 移动 $O(n)$，每个询问 $L$ 移动 $O(B)$，复杂度也是 $O(qB+\frac{n^2}B)$，最优为 $O(n\sqrt q)$。提交记录。

莫队二次离线：P5047 Yuno loves sqrt technology II

求区间逆序对数，可以离线。先按普通莫队的方式排序，然而区间变化时需要求某区间内大于 / 小于一个数的个数，难以做到较低复杂度，需要优化。考虑把区间个数差分成两个前缀的差，再设 $f(x,y),g(x,y)$ 分别表示 $i\in[1,y]$ 中 $a_i>a_x$ 和 $a_i<a_x$ 的个数，则有以下贡献：

• $[L,R]$ 变为 $[L-1,R]$：$g(L-1,R)-g(L-1,L-2)$。
• $[L,R]$ 变为 $[L,R+1]$：$f(R+1,R)-f(R+1,L-1)$。
• $[L,R]$ 变为 $[L+1,R]$：$-g(L,R)+g(L,L-1)$。
• $[L,R]$ 变为 $[L,R-1]$：$-f(R,R-1)+f(R,L-1)$。

可以把所有 $f,g$ 的询问再次离线到 $y$ 上，然后依次枚举 $y$，询问时查询值域上的前缀和即可。由于查询次数为莫队移动次数 $O(n\sqrt q)$，修改次数只有 $n$，因此离散化后使用修改 $O(\sqrt n)$ 查询 $O(1)$ 的值域分块即可做到 $O(n\log n+n\sqrt n+n\sqrt q)$ 的时间复杂度。

这里如果直接存下所有的询问，则空间复杂度为常数不小的 $O(n\sqrt q)$，考虑优化。首先注意到有许多形如 $f(i,i-1),g(i,i-1)$ 的重复询问，可以先预处理出这 $O(n)$ 个值。之后发现每次区间变化剩余贡献的 $y$ 相同，且 $x$ 是一段连续区间，因此只记录区间左右端点即可，这样就做到了 $O(n+m)$ 的空间复杂度，提交记录。

二维莫队：BZOJ2639 矩形计算

求矩形 $\sum t_i^2$，其中 $t_i$ 为 $i$ 在该矩形内出现次数。所求很像莫队能求的东西，因此把询问全部离线下来，依次按三维所在的块和第四维排序，每次暴力修改当前矩形到目标矩形，这时每移动一次就有 $O(n)$ 的时间开销，实现方式与普通莫队类似。（这里及以下提到的维度指询问的参数）

计算一下时间复杂度，对于 $i\in[1,3]$，第 $i$ 维指针的移动次数为 $O(qB+n\times (\frac nB)^{i-1}$)，分别为当前维块内和上一维换块时的移动次数，第四维移动次数就只有 $O(\frac{n^4}{B^3})$。注意到只有 $O(qB+\frac{n^4}{B^3})$ 在瓶颈上，因此以 $B=nq^{-\frac14}$ 平衡得到最优复杂度为 $O(n^2q^{\frac34}+q\log q)$。

当然每一维还可以依赖上一维进行奇偶优化，可以减小常数。另外不是很懂四个参数的优先级，然而经过尝试发现怎么排都行，事实上复杂度分析也不依赖优先级顺序。经过测试，$lx,ly,ry,rx$ 的顺序在本题表现最好，提交记录。

树上莫队：P4074 糖果公园

树上点有点权，单点修改，求路径 $\sum v_i(\sum_{j=1}^{t_i}w_j)$，其中 $v,w$ 给出，$t_i$ 为 $i$ 在该路径上出现次数。所求很像莫队能求的东西，但是莫队在序列上才好做，因此需要把树压成序列，同时要求树上路径可以用区间表示。

考虑用 DFS 括号序，即每个点在进入和回溯时分别记录 $in$ 和 $out$。为了表示路径，这里认为 $in_i,out_i$ 均在区间内时 $i$ 点无贡献，这也可以 $O(1)$ 修改。表示 $in_x<in_y$ 的 $x,y$ 间路径时，先找出两点的 LCA $z$。若 $z=x$ 则 $[in_x,in_y]$ 即所求；否则 $[out_x,in_y]$ 再加上 $z$ 点即所求，在询问上记录附加点即可。

这样就得到了序列长度 $2n$，询问数不变的带修莫队，使用前述做法即可解决，时间复杂度 $O(mn^{\frac 23}+n^{\frac 43})$，实现上有一些细节，提交记录。另外 OIWiki 给出了不压成序列的树上莫队算法，感觉困难，且括号序应该够用了，所以没学。