莫队浅记

· · 个人记录

莫队 （离线算法）

问题：给出一个序列和若干查询 l, r，问 [l, r] 中有多少个不同的数。

排序方式

  1. 对于区间 [l,r] ， 以 l 所在块的编号为第一关键字， r 为第二关键字从小到大排序
O(n sqrt(n)) 
bool cmp(const Node&a,const Node&b)
{
    if(a.l/blo==b.l/blo) return a.r<b.r;
    else return a.l<b.l;
}
  1. 奇偶化排序 ： 对于编号为奇数的块， 令 r 从小到大排序，对于编号为偶数的块，令 r 从大到小排序。

当指针 r 处理完奇数块的问题后，一般情况下会在数组靠末尾的地方，在返回 1 的途中可以处理偶数块的问题，然后再向 n 移动处理下一个奇数块的问题。这么做可以优化 r 指针的移动次数。

```cpp bool cmp(const Node&a,const Node&b) { if(a.l/blo!=b.l/blo) return a.l<b.l; if((a.l/blo)&1) return a.r<b.r; else return a.r>b.r; } ``` 这里 $blo$ 的大小都取 $sqrt(n)$ ，理论上取 $n/sqrt(m)$ 最优 - ### 带修莫队 一般只支持单点修改。 P1903 [国家集训队] 数颜色 / 维护队列 https://www.luogu.com.cn/problem/P1903 这里块大小取 $n^{2/3}$ 时理论复杂度最优。 - ### 树上莫队 法一：将树转化成欧拉序，然后就可以直接在欧拉序（括号序）上跑莫队。 对于一棵节点数为 $n$ 的树，它的欧拉序为一个长度为 $2n$ 的序列，记录了对这棵树 $dfs$ 时一个点 “入搜索栈的时间戳”（记为 $st_i$ ） 与 “出搜索栈的时间戳”（记为 $ed_i$ ） ，以及每个时间戳的对应点（记为 $lis$ ）。 树的欧拉序上两个相同编号（设为 $x$ ）之间的所有编号都出现两次，且都位于 $x$ 子树上。 当询问为一条路径的时候（假设路径两端点为 $( u , v)$ ） 1. 当 $u$ 为 $v$ 的祖先时（前提 $st_u < st_v$ ）： 那么就可以直接在 $lis$ 上跑区间询问为 $[\ st_u , st_v\ ]$ 的莫队，发现其中属于路径的点只遍历了一次，不属于路径的点遍历了两次，这启示我们可以将不在路径上的点利用两次遍历将贡献抵消，我们可以直接在当前点未出现时 $Add$ ，当前点出现过时 $Del$ 。 2. 当 $u$ ，$v$ 没有祖孙关系时（前提 $st_u < st_v$ ）： 那么我们可以在 $lis$ 上跑区间询问为 $[\ ed_u , st_v\ ]$ 的莫队，其中非路径上的点都会遍历两次被抵消，只有路径上的点只会被遍历一次。但是可以发现，此时 $LCA(u,v)$ 并不会被遍历到，那么我们就要对 $LCA(u,v)$ 进行 $Add$ 操作，当前询问的答案记录完毕后再将 $LCA(u,v)$ 进行 $Del$ 操作（因为此时我们维护的只是 $lis$ 上区间的贡献，而 $LCA(u,v)$ 并不在 $lis$ 上的区间内） 当询问为一颗子树时（假设询问的是 $u$ 的子树）： 此时可以在 $lis$ 上跑区间询问为 $[\ st_u , ed_u\ ]$ 的莫队，发现 $u$ 的每一个子树节点都会被找到两次，此时我们并不想让它们抵消，那么我们可以都将其进行 $Add$ 操作（跳出区间就用 $Del$ 操作），注意记录答案的时候要根据实际情况对某些值 $\times2$ 或 $/2

法二：将树进行若干个块，具体操作如 P2325 [SCOI2005]王室联邦 ，这里不展开详讲。

当 Add 操作时间复杂度非常小、 Del 操作时间复杂度非常大（或无法实现）时，就可以利用回滚莫队，只对区间进行 Add 操作，然后根据具体情况将两个指针直接改到某个位置。同理也可以对区间只进行 Del 操作。这里不详讲（我也不会）。

当 Add 与 Del 的操作数时间复杂度非常大时，就可以利用二次离线莫队来降低复杂度，至于详细的，我不会，不讲。

注意：

  1. 先 Add 后 Del 好习惯。

  2. 注意是否以及给 blo 赋值

  3. 带修莫队的块大小切记赋为 n^{2/3}