【学习记录】莫队

· · 个人记录

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

普通莫队：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 的个数，则有以下贡献：

可以把所有 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 给出了不压成序列的树上莫队算法，感觉困难，且括号序应该够用了，所以没学。