基础莫队学习笔记
PikachuQAQ
·
·
算法·理论
引入
上文提到，分块是一种优雅的暴力，能以较优秀的时间复杂度处理各种（或许是线段树做不到的）在线询问。
但涉及到 区间计数 等问题，分块也就无法实现了，如果不强制在线，有没有什么能在较优秀的时间复杂度下，能处理这个问题的算法呢？
简介
莫队是一种能处理多种离线询问的算法，经过拓展可以支持带修，支持树上操作等，同时时间复杂度比较优秀。是另一种优雅的暴力。第一种见 分块学习笔记。
例题
例题 1：P1972 [SDOI2009] HH的项链
Description
由于本篇主要讲莫队，所以本题的数据范围会被缩小到原来的 40\% 数据级别。
给定一个长为 n 的序列 a，q 次询问，每次询问给定两个数 l,r，询问序列 a 中范围 [l,r] 有多少种不同的数。
#### Solution
直入本篇主题：莫队。
莫队的算法流程如下：
首先初始化两个指针 $L=1,R=0$。对于每个询问，尝试将当前指针缩小 / 放大范围到询问区间。
其中，当指针区间缩小时，说明答案缩小了，应减去当前位置答案，随后指针靠近询问区间一个下标。同理，当指针区间放大时，说明答案增多了，应当先靠近询问区间一个下标，再增加当前位置答案。（想一想，区间扩大为什么是先移后增？）
当左右指针都到达询问区间时，答案处理完成。
思考，时间复杂度是多少？
显然，复杂度是可以卡到 $O(nq)$ 的，这种做法并不优。
再思考，再暴力算法中，能优化的只有指针移动，那么是否可以优化处理顺序，使指针移动次数大幅减少？
把指针移动的路线转化到平面图上，大致如下：
于是指针的移动长就转化成了一个求平面最短连接问题。求最短是暂时没有多项式解法的，但是我们可以优化至较短的路径。
考虑以下排序方式：
首先，把 $a$ 分成 $\sqrt{n}$ 块（大多数时）。
令 $id_i$ 为 $i$ 所在块编号，然后将询问离线下来，按 $id_l$ 为第一关键字排序，按 $r$ 为第二关键字排序。
将排序后的 $[l,r]$ 放在平面图上顺次连接后大概长这样：
看上去指针移动的距离优化了很多，至少没有打结了。
事实上，还可以按照 $id_l$ 奇偶性进行排序，即当两个块相邻时，分别按 `a.r < b.r` 和 `a.r > b.r`（或相反）排序，这样路线会更短更平滑，请读者尝试自行理解。
可以看出，每次移动距离不会超过 $2\sqrt{n}$，同时指针肯定不走“回头路”，共 $q$ 次询问，所以总时间复杂度是 $O(n\sqrt{n})$ 的。
对于增加操作，如果增加前计数桶为 $0$，种类数加 $1$。
对于减少操作，如果减少后计数桶为 $0$，种类数减 $1$。
至此，本题的 $40\%$ 做法完毕，通过奇偶优化加卡常加调块长等等操作能卡到 $56pts$。
#### Code
```cpp
// PikachuQAQ 2024/08/20
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e6 + 2;
int id[kMaxN];
int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + (ch - 48);
ch = getchar();
}
return x * w;
}
void write(int x) {
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
struct Q {
int l, r, k;
friend bool operator < (Q a, Q b) {
return (id[a.l] == id[b.l]) ?
((id[a.l] & 1) ? (a.r < b.r) : (a.r > b.r)) :
(id[a.l] < id[b.l]);
}
} b[kMaxN];
int n, q, a[kMaxN], len, res, cnt[kMaxN], ans[kMaxN];
void del(int x) {
res -= (--cnt[a[x]] == 0);
}
void add(int x) {
res += (cnt[a[x]]++ == 0);
}
int main() {
n = read();
const int len = sqrt(n) + 750;
for (int i = 1; i <= n; i++) {
a[i] = read();
id[i] = (i - 1) / len + 1;
}
q = read();
for (int i = 1, l, r; i <= q; i++) {
l = read(), r = read();
b[i] = {l, r, i};
}
sort(b + 1, b + q + 1);
for (int i = 1, l = 1, r = 0; i <= q; i++) {
while (l < b[i].l) del(l++);
while (r > b[i].r) del(r--);
while (l > b[i].l) add(--l);
while (r < b[i].r) add(++r);
ans[b[i].k] = res;
}
for (int i = 1; i <= q; i++) {
write(ans[i]);
putchar('\n');
}
return 0;
}
```
### 例题 2：[P1494 [国家集训队] 小 Z 的袜子](https://www.luogu.com.cn/problem/P1494)
#### Description
给定一个长为 $n$ 的序列 $a$，$q$ 次询问，每次询问给定两个数 $l,r$，在询问区间中随机选取两个数，这两个数相同的概率，用分数表示。如果 $l=r$，输出 `0/1`。
$1 \le n,q,a_i \le 5 \times 10^4$，$1 \le l \le r \le n$。
#### Solution
同上一题的思路。先考虑抽取到相同数的方案数。
- 每次当前颜色增加 $1$ 时，贡献增多了原本的相同颜色的个数，方案数增加它。
- 每次当前颜色减少 $1$ 时，贡献减少了减后的相同颜色的个数，方案数减去它。
令 $f=r-l+1$。
显然，每次询问的总方案数是 $\binom{f}{2}=\dfrac{f(f-1)}{2}$。最后两数约分输出即可，注意 $l=r$ 特判。
#### Code
```cpp
// PikachuQAQ 2024/08/21
#include <bits/stdc++.h>
using namespace std;
using PLL = pair<long long, long long>;
const int kMaxN = 5e4 + 2;
int id[kMaxN];
struct Q {
int l, r, k;
friend bool operator < (Q a, Q b) {
return (id[a.l] == id[b.l]) ?
((id[a.l] & 1) ? (a.r < b.r) : (a.r > b.r)) :
(id[a.l] < id[b.l]);
}
} b[kMaxN];
int n, q, k, a[kMaxN], len, cnt[kMaxN];
long long res;
PLL ans[kMaxN];
void del(int x) {
res -= (--cnt[a[x]]);
}
void add(int x) {
res += (cnt[a[x]]++);
}
PLL frac(int a, int b) {
if (a == 0) return {0, 1};
return {a / __gcd(a, b), b / __gcd(a, b)};
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
len = sqrt(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
id[i] = (i - 1) / len + 1;
}
for (int i = 1, l, r; i <= q; i++) {
cin >> l >> r;
b[i] = {l, r, i};
}
sort(b + 1, b + q + 1);
for (int i = 1, l = 1, r = 0; i <= q; i++) {
while (l < b[i].l) del(l++);
while (r > b[i].r) del(r--);
while (l > b[i].l) add(--l);
while (r < b[i].r) add(++r);
int f = r - l + 1;
ans[b[i].k] = frac(res, 1ll * f * (f - 1) >> 1ll);
}
for_each(ans + 1, ans + q + 1, [](pair<int, int> x){
cout << x.first << '/' << x.second << '\n';
});
return 0;
}
```
### 例题 3：[P1903 [国家集训队] 数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
#### Description
给定一个长为 $n$ 的序列 $a$，$q$ 次操作，有两种操作：
- `Q l r` 表示询问 $[l,r]$ 区间内有几种不同的数。
- `R p c` 表示将第 $p$ 个数改成 $c$。
$1 \le n,q\le 1.5\times 10^5$，$1 \le l \le r \le n$，$1 \le c,a_i \le 10^6$，$1 \le p \le n$。
#### Solution
这个问题有修改了，普通的莫队肯定完不成。
于是请出主角：带修莫队！支持单点修改，区间查询。
可以想到，本题答案的值是按时间的上升而变化的，因此要将询问和修改分开处理，询问需要多一个参数：$t$，来分别处理每个时间的答案。
具体来讲，令时间指针 $T=0$，当当前处理的操作编号小了，就要往大靠拢，再修改，反之先修改，再往小靠拢。
对于每次移动的修改操作，如果当前操作再第 $i$ 个询问范围内，就说明这个修改对答案产生影响。删去原本的数，换成修改的书即可。
那么如何处理交换后的 $a$ 呢？
其实并不麻烦。只需要交换 被替代的数 和 替代原数的数即可，因为修改一个位置多次一定是修改再还原，修改再还原，因此仅需交换。
对于询问排序比较，需要以 $id_l$ 为第一关键字，$id_r$ 为第二关键字，$t$ 为第三关键字进行排序。
但是，块长不再是 $\sqrt{n}$ 了， 因为多一个时间轴时，块长应该是 $n^{\frac{2}{3}}$，时间复杂度为 $O(n^\frac{5}{3})$。[证明见此](https://oi-wiki.org/misc/modifiable-mo-algo/#%E7%89%B9%E7%82%B9)。
至此，本题得解。
#### Code
```cpp
// PikachuQAQ 2024/08/22
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 1e6 + 2;
int id[kMaxN];
char op;
struct Q {
int l, r, t, k;
friend bool operator < (Q a, Q b) {
return (id[a.l] == id[b.l]) ? ((id[a.r] == id[b.r]) ? (a.t < b.t) : (id[a.r] < id[b.r])) : (id[a.l] < id[b.l]);
}
} bq[kMaxN];
struct R {
int p, d;
} br[kMaxN];
int n, q, k, qt, rt, a[kMaxN], len, cnt[kMaxN], res, ans[kMaxN];
void del(int x) {
res -= (--cnt[x] == 0);
}
void add(int x) {
res += (cnt[x]++ == 0);
}
void update(int x, int t) {
if (bq[x].l <= br[t].p && br[t].p <= bq[x].r) {
del(a[br[t].p]);
add(br[t].d);
}
swap(a[br[t].p], br[t].d);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
len = pow(n, 2. / 3.);
for (int i = 1; i <= n; i++) {
cin >> a[i];
id[i] = (i - 1) / len + 1;
}
for (int i = 1, l, r; i <= q; i++) {
cin >> op >> l >> r;
if (op == 'Q') {
bq[++qt] = {l, r, rt, qt};
} else {
br[++rt] = {l, r};
}
}
sort(bq + 1, bq + qt + 1);
for (int i = 1, l = 1, r = 0, t = 0; i <= qt; i++) {
while (l < bq[i].l) del(a[l++]);
while (r > bq[i].r) del(a[r--]);
while (l > bq[i].l) add(a[--l]);
while (r < bq[i].r) add(a[++r]);
while (t < bq[i].t) update(i, ++t);
while (t > bq[i].t) update(i, t--);
ans[bq[i].k] = res;
}
for (int i = 1; i <= qt; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```
### 例题 4：[SP10707 COT2 - Count on a tree II](https://www.luogu.com.cn/problem/SP10707)
#### Description
给定一棵 $n$ 个节点的树，每个节点的权值为 $a_i$。$q$ 次询问，每次询问给定两个节点，问包含 $u,v
之间的路径有多少不同权值。
#### Solution
通过 **欧拉序**，莫队可以升级成树上莫队，通过树链剖分、LCA 等可以维护一些两个节点间的询问。
由于本题权值非常大，需要离散化。
离散化后的样例的图长这样：（花括号里的是权值）
考虑把这个图的欧拉序取出来：
`1 2 2 3 5 5 6 6 7 7 3 4 8 8 4`
我们考虑在欧拉序上操作。
先考虑有了询问区间，如何在欧拉序上操作。
具体来讲，给一个欧拉序区间，比如 $[l,r] = [1,5]$，当一个节点在区间里出现两次时，说明其不在询问路径上，当一个节点出现一次时，说明其在询问路径上。
因此，对于莫队的修改，当一个节点出现一次，且其权值没有出现过，答案加一，否则当一个节点出现过两次，且它没有相同的权值，答案减一。
然后考虑要怎么求出在欧拉序上询问的区间。
令 $s_u$ 为 $u$ 进入的时间，$t_u$ 为 $u$ 出来的时间，默认 $s_u<s_v$。询问分两种情况：
- $u$ 为 $v$ 的 LCA。比如 $u=1,v=7$，如果要让询问包括 $u,v$，应取出来 `1 2 2 3 5 5 6 6 7`，根据上文，被影响的节点是 $\{1,3,7\}$，正好是路径 $[1,7]$ 的所有节点，可观察出询问区间应该是 $[s_u,s_v]$。
- $u$ 不为 $v$ 的 LCA。比如 $u=4,v=5$。如果要让询问包括 $u,v$，应取出来 `5 6 6 7 7 3 4`，被影响的节点是 $\{3,4,5\}$，观察到 $1$ 在路径上但没有被算进去，因为两点的 LCA 会被算两遍，所以在计算答案时也要算 LCA。可以观察出询问区间是 $[t_u,s_v]$。
因此，询问区间就分讨完了。
最后，将询问按 $\sqrt{q}$ 分块，排序后处理答案即可。
#### Code
```cpp
// PikachuQAQ 2024/08/30
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 4e4 + 2, Lg = 24, kMaxQ = 1e5 + 2;
struct Q {
int l, r, k, lca, p;
friend bool operator < (Q a, Q b) {
return (a.p == b.p) ?
((a.p & 1) ? (a.r < b.r) : (a.r > b.r)) :
(a.p < b.p);
}
} b[kMaxQ];
int n, q;
int m, a[kMaxN], c[kMaxN], df;
int s[kMaxN], t[kMaxN], edfn[kMaxN << 1], dfn[kMaxN];
int ts, p[Lg][kMaxN], dep[kMaxN];
int res, cnt[kMaxN];
vector<int> g[kMaxN];
bool vis[kMaxN];
int ans[kMaxQ];
void disc() {
for (int i = 1; i <= n; i++) c[i] = a[i];
sort(c + 1, c + n + 1);
m = unique(c + 1, c + n + 1) - c - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(c + 1, c + m + 1, a[i]) - c;
}
void update(int x) {
vis[x] ^= 1;
res -= (vis[x] == 0 && (--cnt[a[x]] == 0));
res += (vis[x] && (++cnt[a[x]] == 1));
}
int get(int u, int v) { return dfn[u] < dfn[v] ? u : v; }
void DFS(int u, int fa) {
p[0][dfn[u] = ++ts] = fa, edfn[s[u] = ++df] = u;
for (int v : g[u]) if (v ^ fa) DFS(v, u);
edfn[t[u] = ++df] = u;
}
int LCA(int u, int v) {
if (u == v) return u;
if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
int d = __lg(v - u++);
return get(p[d][u], p[d][v - (1 << d) + 1]);
}
void init() {
DFS(1, 0);
for (int i = 1; i <= __lg(n); i++)
for (int j = 1; j + (1 << i) - 1 <= n; j++)
p[i][j] = get(p[i - 1][j], p[i - 1][j + (1 << i - 1)]);
}
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> q;
static const int len = sqrt(q);
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1, u, v; i < n; i++) {
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
disc(), init();
for (int i = 1, u, v, lca; i <= q; i++) {
cin >> u >> v, lca = LCA(u, v);
if (lca == u || lca == v) {
if (s[u] > s[v]) swap(u, v);
b[i] = {s[u], s[v], i, 0, s[u] / len};
} else {
if (s[v] > t[u]) swap(u, v);
b[i] = {t[u], s[v], i, lca, t[u] / len};
}
}
sort(b + 1, b + q + 1);
for (int i = 1, l = 1, r = 0; i <= q; i++) {
while (l < b[i].l) update(edfn[l++]);
while (r > b[i].r) update(edfn[r--]);
while (l > b[i].l) update(edfn[--l]);
while (r < b[i].r) update(edfn[++r]);
if (b[i].lca) update(b[i].lca);
ans[b[i].k] = res;
if (b[i].lca) update(b[i].lca);
}
for (int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```
## 后记
莫队真挺好玩的，是考场上针对相邻区间转移答案复杂度非常小 (小于等于 $\log n$)，询问离线的骗分利器。