莫队学习笔记

· · 算法·理论

莫队

莫队是个好东西

莫队简介

莫队算法是由莫队提出的。虽然他提出之前该算法已经在Codeforces中小范围流传，但是莫涛是第一个详细总结莫队算法的人。

莫队作用

莫队是一种离线处理静态区间查询的一类方法。时间复杂度为 O(n\sqrt{q}+q\log q)，当 n,q 同阶时复杂度为 O(n\sqrt{n})。

普通莫队

形式

钦定 n,m 同阶，那么对于区间询问问题，从 [l,r] 的答案 O(1) 扩展到 [l\pm1,r\pm1]（即与 [l,r] 相邻的区间）的答案，那么可以 O(n\sqrt{n}) 求出所有询问的答案。详细看解释。

解释

离线后按照特定的方式排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间的答案（一步一步的将 l,r 指针移动即可）。

那么有人就要问了：这样子的时间复杂度在 n,q 同阶时不就是 O(n^2) 吗？

实际上不是。注意到上面描述作用时，有一个 O(q\log q)。容易看出是排序的时间复杂度，也就是说，我们在指针移动之前要排序。

排序方法

我们把问题变成一个简单的理解就是在平面坐标系上游走，有 q 个目标点 (l_i,r_i)，需要找到总长度最短的路径经过每个目标点一次。

很容易想到，如果 l_i,r_i 分别单调递增，则用双指针即可 O(n) 维护这个问题。但是，如果我们放宽一下，允许 l 在小范围内移动，r 单增。其中，小范围看成分块。那么，排序方法就为按 l 所在的块为第一关键字，r 为第二关键字，将所有询问排序。

但是我们的时间复杂度得到优化了吗？如果块长为 T，那么每次询问，l 指针的移动量为 O(T) 的，总移动量 O(qT)，r 指针在 l 不换块的时候是单调的，总移动量是 O(\frac{n}{T}\times n)。根据均值不等式求出当 T=\frac{n}{\sqrt{q}} 时复杂度为 O(n\sqrt{q}+q\log q)。

tips：关键字的意思是指从小到大排序时的依据，也就是按照谁的值来排序的。

代码

处理每个询问（先扩张在缩小，避免区间为空）

// 回答 [l,r]，当前在 [L,R]
while(L > l) add(-- L);
while(R < r) add(++ R);
while(L < l) del(L ++);
while(R > r) del(R --);

排序方法（重载）

struct node {
    int l, r, id;
    //b[x] 表示 x 所在的块
    bool operator < (const node &x) const {
        if (b[l] ^ b[x.l]) return l < x.l;
        else return r < x.r;
    }
};

优化

过程

这里我们要用到奇偶化排序。

什么是奇偶化排序？奇偶化排序即对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样我们的 r 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 n 移动处理下一个奇数块的问题，优化了 r 指针的移动次数。

建议自己模拟一下，加深理解。

代码

struct node {
  int l, r, id;
  bool operator<(const node &x) const {
    if (l / unit ^ x.l / unit) return l < x.l;
    if ((l / unit) & 1) return r < x.r;
    return r > x.r;
  }
};

习题

P1494 [国家集训队] 小 Z 的袜子

带修改莫队

普通莫队处理的都是静态问题，如果加上单点修改还能做吗？

充分发挥人类智慧。 我们可以认为是多了“时间”这一个维度，也就是询问形如 (l,r,t) 表示询问进行了 t 次单点修改之后，区间 [l,r] 的答案。

也就是变成了在一个三维的坐标系中游走，但是我们需要对这样的询问再后再一个排序的方式使其复杂度优于暴力。

其实我们只需要把时间也看成指针。特别地，如果加入的修改在当前区间里面，应当立刻对区间答案进行修改处理影响。

先按 l_i 所在块的编号排序，第二关键字是 r_i 所在块的编号，第三关键字才是 t_i。

那么复杂度又是多少呢？

钦定 n,m 同阶时，令块长 T=n^{\frac 23}，则有 n^{\frac 13} 个块。当 l,r 所在的块固定时，时间指针只会移动 O(n) 次。而 l,r 所在的块的组合仅有 O((n^{\frac13})^2) 个，于是时间指针的中移动量为 O(n^{\frac53})，l,r 的总移动量都是 n^{\frac13}\times(n^{\frac23})^2=n^{\frac53}，因此总时间复杂度是 O(n^{\frac53})。

P1903 [国家集训队] 数颜色 / 维护队列

回滚莫队

我们发现无论是普通莫队还是带修改莫队，都可以快速地对区间进行扩展或者收缩。

如果强行想用莫队做区间最大值等增加或删除无法实现的问题怎么办？

当只增加和删除中的一个不可实现时，就可以使用回滚莫队 O(n\sqrt{q}) 时间解决。

核心

只能使用一种操作，就用一种操作，剩下的用回滚莫队来解决。

形式

假设现在只能区间扩展，不能删除（只删除不扩展是类似的）。

那么，我们怎么样让 l 这一坨只加入不删除呢？我们始终让 l 保持在当前它所在的区间的右端点，然后 r 已知移动到询问的 r_i，然后 l 再移动到 l_i。

走了之后我们所做的操作不叫删除，叫回退。回退就是我们知道我们走的时候的状态，然后一步一步回到这个状态。

举个栗子：比如你修改了 [l,r] 的 \max 值，你在移动到 [l,r+1] 前备份你的最大值。

参考文献及鸣谢

本文部分内容参考oi-wiki上的内容。

特别感谢@摸鱼酱@Aurelia_Veil@chenyixuan18提供的宝贵意见。

欢迎在下方留言哦。