莫队算法

莫队算法是由莫涛首先总结的一种处理可离线、不带修、移动边界时间复杂度接近 \(O(1)\) 的问题的算法。

简介

这就做完了。

很惊讶？我们来看看复杂度证明。

先约定 \(n\) 表示序列的长度，\(m\) 表示询问个数，设块长为 \(L\)：

块内左端点移动：单次最多 \(O(L)\) 次，一共移动了 \(m\) 次，因此总共是 \(O(mL)\) 的。
块内右端点移动：由于右端点有序，同一块内是 \(O(n)\) 的，一共有 \(\frac{n}{L}\) 块，因此总共为 \(O(\frac{n^2}{L})\)。
块间移动：显然单次不超过 \(O(n)\)，一共 \(\frac{n}{L}\) 次。因此总共 \(O(\frac{n^2}{L})\)。

总复杂度是 \(O(mL+\frac{n^2}{L})\) 的。根据基本不等式，该式在 \(L=\frac{n}{\sqrt{m}}\) 时取得最小值 \(\frac{n}{\sqrt{m}}\)。

综上所述，将块长分为 \(\frac{n}{\sqrt{m}}\) 时，理论时间复杂度达到最小值 \(O(\frac{n}{\sqrt{m}})\)。

你可能注意到我们在计算过程中忽略了常数。但是常数是无所谓的，毕竟倘若数据比较水的话，莫队的耗时远远达不到其上界，因此常数多大还得看数据，分块的长度影响并不大。

将数按照 DFS 序摊成“括号序列”（我也不知道叫什么名字）。就是说，进入和离开该点的子树时该点在序列上出现一次，例如如图就是12233441。

如果查询 \(a,b\) 路径上的答案，你就从 \(a\) 第二次出现的位置到 \(b\) 第一次出现的位置做莫队查询（除非LCA在a上，此时从 \(a\) 第一次出现的位置出发）。要统计一个点出现的次数，如果某个点经过了两次，就说明它不在链上，因此要把它的贡献去掉。

如果这种问题可以撤销元素，但是不能（快速地）删除元素（也就是说，可以撤销刚刚进行的操作，但不能删除很久之前的操作并把后面的保留），那么我们就使用回滚莫队。

对于一种没有跨块的询问，我们单独处理。

对于跨块的询问，设块的右边界是 \(x\)，我们先扩展至 \((x,r_1)\)，然后再扩展至 \((l_1,r_1)\)，最后再撤销回 \((x,r_1)\)（用 vector 存修改）。注意到复杂度和原来没变。

对于带修的莫队查询，我们加入一个时间维度，并在挪动查询区间边界时，也挪动它的所在时刻。分块的块长要改为 \(n^{\frac{2}{3}}\) 复杂度才最优。

莫队可以结合 \(O(1)\) 修改，查询复杂度较大的数据结构，如分块、bitset。

有些莫队中无法做到 \(O(1)\) 修改时，比如修改需要额外的信息而我不知道，可以把修改所需的信息当成询问离线（通常配合差分拆成一个前缀询问，和一个前缀-单点询问），用另一离线算法计算。好史

这里根号分治、分块非常频繁地出现，因为它们是很好的 \(O(n\sqrt{n})\) 的离线算法。根号分治一般用于倍数问题。有时还有把二次离线的询问绑成一组一组的情况（点名 P5398 [Ynoi2018] GOSICK - 洛谷）。