莫队&莫队小进阶
prh_rpjiajia
·
·
算法·理论
最近在学习莫队，因此来写篇文章，记录。
莫队
简介
莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。
莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。
基本形式
离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步一步移动即可）。
普通莫队解题思路
- 我们将每个询问左端点所在的块编号作为第一关键字，将右端点作为第二关键字，然后进行排序。
- 对于左右端点在同一块内，我们暴力处理。
- 先将右指针移动到当前询问右端点，记录当前答案 temp=ans。
- 再将左指针移动到当前询问左端点，记录当前答案 ans 即当前询问答案。
- 我们将左指针回滚到当前块右端点 +1，并将答案 ans 重新变回 temp。
- 若下一个询问左端点所在的块不同，则将左指针移动到下一个询问左端点所在的块 +1，右指针移动到左指针 -1，并将 ans 赋值为 0。
提醒一句： 莫队代码不长（或者说是很短），但很容易写错一些细节。比如自加自减运算符的优先级问题、排序关键字问题、分块大小与 sqrt 精度问题、还有某些题目中用到的离散化的锅。所以每次码完莫队都别先测样例（甚至可以先不编译），先静态查错一阵，真的可以帮助你大大减少错误的发生。
时间复杂度
令每一块中 L 的最大值为 \max_1,\max_2,\max_3, \cdots , \max_{\lceil\sqrt{n}\rceil}。由第一次排序可知，\max_1 \le \max_2 \le \cdots \le \max_{\lceil\sqrt{n}\rceil}。
显然，对于每一块暴力求出第一个询问的时间复杂度为 O(n)。
考虑最坏的情况，在每一块中，R 的最大值均为 n，每次修改操作均要将 L 由 \max_{i - 1} 修改至 \max_i 或由 \max_i 修改至 \max_{i - 1}。
考虑 R：因为 R 在块中已经排好序，所以在同一块修改完它的时间复杂度为 O(n)。对于所有块就是 O(n\sqrt{n})。
重点分析 L：因为每一次改变的时间复杂度都是 O(\max_i-\max_{i-1}) 的，所以在同一块中时间复杂度为 O(\sqrt{n}\cdot(\max_i-\max_{i-1}))。
将每一块 L 的时间复杂度合在一起，可以得到：
对于 L 的总时间复杂度为
& O(\sqrt{n}(\max{}_1-1)+\sqrt{n}(\max{}_2-\max{}_1)+\sqrt{n}(\max{}_3-\max{}_2)+\cdots+\sqrt{n}(\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1))} \\
= \phantom{} & O(\sqrt{n}\cdot(\max{}_1-1+\max{}_2-\max{}_1+\max{}_3-\max{}_2+\cdots+\max{}_{\lceil\sqrt{n}\rceil-1}-\max{}_{\lceil\sqrt{n}\rceil-2}+\max{}_{\lceil\sqrt{n}\rceil}-\max{}_{\lceil\sqrt{n}\rceil-1)}) \\
= \phantom{} & O(\sqrt{n}\cdot(\max{}_{\lceil\sqrt{n}\rceil-1}))\\
\end{aligned}
（裂项求和）
[小试牛刀](https://htoj.hetao101.com/cpp/oj/problem/detail?pid=22069044704640)。
根据莫队原理，写出如下主体代码：
```cpp
int aa[maxn], cnt[maxn], l = 1, r = 0, now = 0; //每个位置的数值、每个数值的计数器、左指针、右指针、当前统计结果（总数）
void add(int pos) {//添加一个数
if(!cnt[aa[pos]]) ++now;//在区间中新出现，总数要+1
++cnt[aa[pos]];
}
void del(int pos) {//删除一个数
--cnt[aa[pos]];
if(!cnt[aa[pos]]) --now;//在区间中不再出现，总数要-1
}
void work() {
for(int i = 1; i <= q; ++i) {//对于每次询问
int ql, qr;
scanf("%d%d", &ql, &qr);//输入询问的区间
while(l < ql) del(l++);//如左指针在查询区间左方，左指针向右移直到与查询区间左端点重合
while(l > ql) add(--l);//如左指针在查询区间左端点右方，左指针左移
while(r < qr) add(++r);//右指针在查询区间右端点左方，右指针右移
while(r > qr) del(r--);//否则左移
printf("%d\n", now);//输出统计结果
}
}
```
### 玄学卡常技巧
#### 1.莫队玄学性奇偶排序
这个和莫队的主算法有异曲同工之妙……看起来什么用都没有，实际上可以帮你每个点平均优化200ms。
**主要操作：**
这是之前查询区间的排序函数：
```cpp
int cmp(query a, query b)
{
return belong[a.l] == belong[b.l] ? a.r < b.r : belong[a.l] < belong[b.l];
}
```
咱们把它换成：
```cpp
int cmp(query a, query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
```
也就是说，对于左端点在同一奇数块的区间，右端点按升序排列，反之降序。这个东西也是看着没用，但实际效果显著。
它的主要原理便是右指针跳完奇数块往回跳时在同一个方向能顺路把偶数块跳完，然后跳完这个偶数块又能顺带把下一个奇数块跳完。理论上主算法运行时间减半，实际情况有所偏差。
#### 2.移动指针的常数压缩
根据运算符优先级的知识，把这个：
```cpp
void add(int pos) {
if(!cnt[aa[pos]]) ++now;
++cnt[aa[pos]];
}
void del(int pos) {
--cnt[aa[pos]];
if(!cnt[aa[pos]]) --now;
}
```
和这个：
```cpp
while(l < ql) del(l++);
while(l > ql) add(--l);
while(r < qr) add(++r);
while(r > qr) del(r--);
```
压缩成：
```cpp
while(l < ql) now -= !--cnt[aa[l++]];
while(l > ql) now += !cnt[aa[--l]]++;
while(r < qr) now += !cnt[aa[++r]]++;
while(r > qr) now -= !--cnt[aa[r--]];
```
恭喜你，又优化了200ms。
**小试牛刀的参考代码代码（不许抄！！）：**
```cpp
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define maxn 1010000
#define maxb 1010
int aa[maxn], cnt[maxn], belong[maxn];
int n, m, size, bnum, now, ans[maxn];
struct query {
int l, r, id;
} q[maxn];
int cmp(query a, query b) {
return (belong[a.l] ^ belong[b.l]) ? belong[a.l] < belong[b.l] : ((belong[a.l] & 1) ? a.r < b.r : a.r > b.r);
}
#define isdigit(x) ((x) >= '0' && (x) <= '9')
int read() {
int res = 0;
char c = getchar();
while(!isdigit(c)) c = getchar();
while(isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar();
return res;
}
void printi(int x) {
if(x / 10) printi(x / 10);
putchar(x % 10 + '0');
}
int main() {
scanf("%d", &n);
size = sqrt(n);
bnum = ceil((double)n / size);
for(int i = 1; i <= bnum; ++i)
for(int j = (i - 1) * size + 1; j <= i * size; ++j) {
belong[j] = i;
}
for(int i = 1; i <= n; ++i) aa[i] = read();
m = read();
for(int i = 1; i <= m; ++i) {
q[i].l = read(), q[i].r = read();
q[i].id = i;
}
sort(q + 1, q + m + 1, cmp);
int l = 1, r = 0;
for(int i = 1; i <= m; ++i) {
int ql = q[i].l, qr = q[i].r;
while(l < ql) now -= !--cnt[aa[l++]];
while(l > ql) now += !cnt[aa[--l]]++;
while(r < qr) now += !cnt[aa[++r]]++;
while(r > qr) now -= !--cnt[aa[r--]];
ans[q[i].id] = now;
}
for(int i = 1; i <= m; ++i) printi(ans[i]), putchar('\n');
return 0;
}
```
## 莫队进阶——回滚莫队
有些题目在区间转移时，可能会出现增加或者删除无法实现的问题。在只有增加不可实现或者只有删除不可实现的时候，就可以使用回滚莫队在 $O(n \sqrt m)$ 的时间内解决问题。回滚莫队的核心思想就是：既然只能实现一个操作，那么就只使用一个操作，剩下的交给回滚解决。
回滚莫队分为只使用增加操作的回滚莫队和只使用删除操作的回滚莫队。以下仅介绍只使用增加操作的回滚莫队，只使用删除操作的回滚莫队和只使用增加操作的回滚莫队只在算法实现上有一点区别。
回滚莫队，可以用来处理一些单向操作简单而反向操作较难的问题，如插入简单，而删除困难的问题。（如要求 `max` ，插入可以直接比较最大值，而删除需要找次大值）即在莫队的四种移动边界的操作中，$[l,r]$ 可以快速转移到 $[l-1,r]$ 或 $[l,r+1]$，而不能方便地转移到 $[l+1,r]$ 和 $[l,r-1]$。（或反之）
设序列长度为 $n$，每块长度为 $a$，共有 $\frac{n}{a}$ 块,$m$ 次询问循环 $1 \le i \le \frac{n}{a}$，找到所有左端点在第 $i$ 块的询问 $l,r$ 若 $r$ 也在第 $i$ 块,那么就暴力求,时间复杂度 $O(\frac{a}{m})$ 否则，右端点用指针 $j$ 维护，左端点每次回到第 $i$ 块的右端，暴力求，时间复杂度 $O(am+\frac{n^2}{a})$ 总时间复杂度 $O(am+\frac{n^2}{a})$。
此处借鉴，@[清风](https://www.acwing.com/user/myspace/index/139576/)。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, INF = 2e9;
int n, m, len;
int w[N], ans[N];
int first[N], last[N];
int rfirst[N], rlast[N];
vector<int> nums;
struct Node {
int id, l, r;
}q[N];
int get(int i)
{
return i / len;
}
bool cmp(Node a, Node b)
{
int al = get(a.l), bl = get(b.l);
if (al != bl)return al < bl;
return a.r < b.r;
}
void add(int x, int& res, int a[N], int b[N], int flag)
{
a[w[x]] = min(a[w[x]], x);
b[w[x]] = max(b[w[x]], x);
res = max(res, b[w[x]] - a[w[x]]);
if (flag)res = max(res, rlast[w[x]] - a[w[x]]);
}
int main()
{
scanf("%d", &n);
len = sqrt(n);
for (int i = 1; i <= n; i ++ )scanf("%d", &w[i]), nums.push_back(w[i]);
sort(nums.begin(), nums.end());
nums.erase(unique(nums.begin(), nums.end()), nums.end());
for (int i = 1; i <= n; i ++ )
w[i] = lower_bound(nums.begin(), nums.end(), w[i]) - nums.begin();
scanf("%d", &m);
for (int i = 1; i <= m; i ++ )
{
int l, r;
scanf("%d%d", &l, &r);
q[i] = {i, l, r};
}
sort(q + 1, q + m + 1, cmp);
memset(first, 0x3f, sizeof first);
memset(last, 0, sizeof last);
for (int x = 1; x <= m;)
{
memset(rfirst, 0x3f, sizeof first);
memset(rlast, 0, sizeof last);
int y = x;
while (y <= m && get(q[x].l) == get(q[y].l))y ++ ;
int right = get(q[x].l) * len + len - 1;
while (x < y && q[x].r <= right)//段内暴力
{
int res = 0;
int id = q[x].id, l = q[x].l, r = q[x].r;
for (int i = l; i <= r; i ++ )add(i, res, first, last, 0);
ans[id] = res;
for (int i = l; i <= r; i ++ )first[w[i]] = INF, last[w[i]] = 0;
x ++ ;
}
int res = 0;
int i = right + 1, j = right;
while (x < y)
{
int id = q[x].id, l = q[x].l, r = q[x].r;
while (j < r)j ++ , add(j, res, rfirst, rlast, 0);
int backup = res;//备份
while (i > l)i -- , add(i, res, first, last, 1);
ans[id] = res;
while (i < right + 1)first[w[i]] = INF, last[w[i]] = 0, i ++ ;//回滚
res = backup;
x ++ ;
}
}
for (int i = 1; i <= m; i ++ )printf("%d\n", ans[i]);
return 0;
}
```
练习：
1. LGP1494。
2. LGP1903。