优雅的暴力——莫队算法
缘起
区间询问是ACM/OI 中常见的问题. 为此, 神犇发明了诸如线段树、树状数组、主席树（以及各种持久化数据结构）、树套树等等数据结构. 但是众所周知，诸如树套树这种数据结构容易手滑打错，而且不方便调试. 因此，就诞生了分块这种神奇的暴力——通过类似于均值不等式的方式将复杂度控制在小于O(n2)之内. 而分块这种思想又诞生了诸如块链、块状树、莫队这些算法. 本文就入门一下莫队这种神奇而优雅的暴力算法. 例题是 洛谷2709 小B的询问
分析
题目描述 小B 有一个长为 n 的整数序列 a，值域为 [1,k]。 他一共有 m 个询问，每个询问给定一个区间 [l,r]，求：
其中 c_i表示数字 i 在 [l,r] 中的出现次数。 小B请你帮助他回答询问。 输入格式 第一行三个整数 n,m,k。 第二行 n 个整数，表示 小B 的序列。 接下来的 m 行，每行两个整数 l,r。 输出格式 输出 m 行，每行一个整数，对应一个询问的答案。 输入输出样例 输入 #1复制 6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6 输出 #1复制 6 9 5 2 说明/提示 【数据范围】 对于 100% 的数据，1≤n,m,k≤5e4
莫队算法是一种可以解决大部分区间问题的离线算法. 在序列中，莫队算法号称 可以解决一切区间问题
之所以叫莫队，是因为该算法的发明人是莫涛大佬 or2
莫队的思想源于分块，所以莫队的复杂度是 , 复杂度不算太差，除非毒瘤，不然不会卡莫队. 而且（离线）莫队真的超好写~
先不论本题，而是看下面这道极为简单的例题
对于一个数列，每次给出询问区间[L, R], 询问数列在[L, R]区间和.
有大佬会说显然用前缀和，但这并不是主题，因为前缀和的思想源于抵消，上面这道简单的题目只是为了引出莫队算法. 首先，我们开一个数组a来存储数列
为了符合离线的姿势，我们自然是这么处理问题的:
如果你现在知道[2, 5]的区间和是18，现在问你[2, 6]的区间和, 你会怎么做?
很简单， [2, 5]的答案加上a[6]不就是 [2, 6] 的答案了吗? 所以答案是 18+4=22
同理，[2, 4]的答案呢? 不就是 [2, 5] 区间的答案减去 a[5] 么? 就是 18-7=11
于是, [3, 6]的答案就是[2,5]的答案减去a[2]加上a[6], 所以[3, 6]的答案是 18-8+4=14
其他区间以此类推
下面把上面的举例抽象化一下
[L,R] 表示当前的区间, 则有以下四种情况
- add(--L) 表示加上当前区间左边一个的贡献
- add(++R) 表示加上当前区间右边一格的贡献
- sub(L++) 表示减去当前区间最左一格的贡献
- sub(R--) 表示减去当前区间最右一格的贡献
注意，add、sub的复杂度最好控制在O(1), 最多不能超过O(log n), 不然莫队复杂度会原地爆炸.
也就是我们通过一格一格的挪窝儿，就能挪出我们想询问的区间的答案.
但是只是这样还是远远不够的, 因为如果我像下面这样询问 2m次:
[1, 2], [n-1, n];
[1, 2], [n-1, n];
...
[1, 2], [n-1, n];
[1, 2], [n-1, n];
因为我们是一格一格的挪动的，所以处理这些询问的复杂度就是O(nm), 被卡成翔了~ 一个自然的优化就是离线这些询问然后排序. 也就是，我们这样询问 2m次
[1,2],[1,2],...,[1,2]
[n-1, n],[n-1,n],....,[n-1,n]
那么复杂度降低为 O(m+n) 的, 这显然可以接受的.
好了，大家已经大概有个认识，莫队算法大概就是 离线所有询问然后排序，所以这样的（普通）莫队不能资瓷修改，下面来讲一下（普通）莫队算法的细节.
排序的准则如下，首先分块，块大小是 , 然后对询问排序, 排序的准则是这样的. 对于询问 [L, R], L所在块的编号是第一关键字，R的大小是第二关键字. 注意，这并不是 C++ stl 的pair<int, int> 的排序规则, 因为比如[3, 7]和[4, 6], 3和4如果在同一个分块的话，则[4, 6] 依旧排在[3, 7]的前面，但是如果按照C++ stl pair<int,int> 的排序规则的话，则[4, 6]应该排在[3, 7]的后面, 所以两种排序规则并不相同.
将所有询问排序好了之后要做的事情自然是遍历排序好的询问, 然后按照刚刚说的 add、sub 方法进行答案的记录，最后输出答案即可.
下面来看看莫队算法的框架——对于（不带修改的）莫队的题目，主要的框架其实是一样的.
int n, m, a[maxn], pos[maxn], ans[maxm], res; // pos[i] = j 含义是a[i]所在分块编号为j.a[1,..,n], m个询问, 长度为n的序列
struct Q
{
int l, r, id; // 该询问[l, r], 是第id个询问
} qs[maxm];
ilv md()
{
int sz = sqrt(n); // 块大小
for(re i = 1; i <= n; i++)
{
read(a[i]);
pos[i] = （i - 1） / sz + 1; // 分块
}
for(re i = 1; i <= m; i++)
{
read(qs[i].l), read(qs[i].r);
qs[i].id = i; // 离线所有询问
}
sort(qs + 1, qs + m + 1, [](Q &x, Q &y) { // 排序所有询问
return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
});
int l = 1, r = 0; // 初始化 [l, r] 为一个空的闭区间.全局变量res维护的就是[l, r]内询问的值
for(re i = 1; i <= m; i++)
{
while(q[i].l < l) add(--l); // add、sub(也就是上面说的一格一格的挪窝儿)的时候维护res
while(q[i].r > r) add(++r);
while(q[i].l > l) sub(l++);
while(q[i].r < r) sub(r--);
ans[q[i].id] = res;
}
for(re i = 1; i <= m; i++) // 输出答案
{
writeln(ans[i]);
}
}基本上使用不带修莫队切的题目的代码风格就是上面的样子，因题目而异的部分就是add、sub函数.
那么我们思考一下，为什么莫队要按照第20行的排序方式进行排序呢? 回到我们的痛点——不就是怕挪窝儿的次数太多了吗? 所以我们的排序规则的唯一目的就是让挪动的次数尽可能的少.
首先想一种直观的解决方法——让所有询问按照左端点升序排序，但是这样的话，我们仅仅能保证左端点不会反向移动，但是右端点在最坏的情况下依旧有可能从最前面移动到最后面或者从最后面移动到最前面, 复杂度依旧是原地爆炸的O(nm), 这样依旧是不行的.
而如果采用伪代码20行的规则排序过后的询问, 刚刚说到的 (l1, r1), (l2, r2) , l1 < l2, r1 比较大而 r2 比较小，l1 、l2相差不大的情况下，l1、l2 很可能在同一个块中，则(l1, r1) 就排在 (l2, r2)后面了, 就不会出现右端点反向移动的情形, 这算是我们对不带修莫队复杂度的一种直观认识. 至于不带修莫队复杂度的证明，见附录.
正因为20行的排序规则，所以莫队才被称为优雅的暴力
现在来看本题该怎么切. 本题是不带修改的莫队的板题.
前面已经说了，不带修改的莫队的题目，算法的框架都是一样的, 对于不同的题目只需要考虑add、sub以及res的意义就好了. 而且注意尽量将add、sub的复杂度控制在O(1)内.
显然，对于本题，需要开一个cnt数组维护各个数字出现的次数. 那么add、sub就很好写了.
//#include "stdafx.h"
//#define LOCAL
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;
#define int long long
#define re register int
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define SQUARE(x) ((x) * (x))
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ilv read(int &x)
{
x = 0; int f = 1; char c = gc();
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ilv read(char *x)
{
char c = gc();
while(!isalpha(c)) c = gc();
while (isalpha(c)) *x++ = c, c = gc();
*x = 0;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
} using namespace fastio;
const int maxn = 5e4;
int n, m, k, res, a[maxn], cnt[maxn], ans[maxn], pos[maxn], sz;
struct Q
{
int l, r, id;
} qs[maxn];
ilv kk(int i, int flag)
{
int t = cnt[a[i]];
cnt[a[i]] += flag;
res += SQUARE(cnt[a[i]]) - SQUARE(t);
}
signed main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
//freopen("d:\\my.out", "w", stdout);
#endif
read(n), read(m), read(k);
sz = sqrt(n * 1.0);
for (re i = 1; i <= n; i++)
{
read(a[i]);
pos[i] = (i - 1) / sz + 1;
}
for (re i = 1; i <= m; i++)
{
read(qs[i].l), read(qs[i].r);
qs[i].id = i;
}
sort(qs + 1, qs + m + 1, [](Q &x, Q &y){
return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
});
int l = 1, r = 0;
for (re i = 1; i <= m; i++)
{
while(qs[i].l < l) kk(--l, 1);
while(qs[i].r > r) kk(++r, 1);
while(qs[i].l > l) kk(l++, -1);
while(qs[i].r < r) kk(r--, -1);
ans[qs[i].id] = res;
}
for (re i = 1; i <= m; i++) writeln(ans[i]);
flush();
return 0;
}ac情况
所属题目 P2709 小B的询问 评测状态 Accepted 评测分数 100 编程语言 C++14 代码长度 2.32KB 用时 1.65s 内存 7.52MB
拓展
本文仅仅介绍了最简单的莫队算法，其实莫队博大精深. 据笔者的浅陋之识来看，莫队分为
- 不带修莫队（本文）
- 带修莫队，一般是单点修改
- 树上莫队
- 在线（带修或不带修）莫队
- 二维莫队
- 二次离线莫队
带修莫队其实就是在不带修莫队的基础上添加了一根时间轴, 对当前询问区间进行add/sub 之前先将尚未进行的修改操作执行（时光演进）或者提前执行的修改操作撤回（时光倒流）. 比较经典的题就是 bzoj 2120 数颜色
关于树上莫队，因为莫队的基石是分块，树上分块的姿势很多，适用于树上莫队的分块有王室联邦树上分块或者括号序将树强制压成一维然后在括号序上跑序列莫队，所以树上莫队一般有两种做法. 比较经典的题就是 洛谷 P4074 WC2013 糖果公园
关于在线莫队，它的缘起是因为莫队要求离线，如果题目强制在线的话，则逼你写树套树容易wa的颓零，这时候，在线莫队这种骗分神器就来了. 它的本质思想依旧源于离线莫队, 因为我们回顾一下莫队为什么要离线? ——因为我们将所有询问离线排好序，然后每一次从上一个询问区间转移过来，但是题目强制在线的话，则从上一个询问区间转移过来变得不可行。所以我们需要预先处理好**某些均匀分布在序列中的区间（称之为特征区间）**的答案，让这些特征区间成为莫队中的"上一个区间”, 然后在线回答询问的时候，让询问区间的答案从这些特征区间的答案转移过来而不是从上一个询问区间的答案转移过来.
关于二维莫队，其实就类似于二维树状数组和树状数组的关系，典型题目见 bzoj 2639.矩形计算
关于二次离线莫队，笔者比较菜，还没有学到.
小结
莫队算法具有暴力算法的最基本而且公共的性质——代码好打~ 而莫队用到的分块也是公认的暴力算法，但是分块&莫队真心是好写又好用啊~ 值得入手~
如果您理解了这里莫队处理区间询问的方法的话，RMQ问题就可以使用分块来处理了~
总之，分块&莫队是很腻害的算法~ 但是这并不是不继续学其他区间算法的理由，共勉！！！