莫队
Contents
介绍
莫队算法是一种基于分块思想的暴力算法，一般应用于同时满足以下条件的区间问题中：
- 已知 $[L,R]$ 之间的答案，能在 $O(1)$ 时间内转移到 $[L+1,R], [L-1,R], [L,R+1], [L,R-1]$ 的答案。
- 所有询问均离线。
- 不存在修改。
我们用模版举个例子：
题意
给定一个长度为 $N$ 的正整数序列 $a$，给定一个 $k$，满足 $\forall i, a_i \in [1,k]$。
现在有 $M$ 个询问，每个询问给定一个区间 $[l,r]$，求 $\sum_{i=1}^kc_i^2$
其中 $c_i$ 为数字 $i$ 在 $[l,r]$ 中的出现次数。
数据范围：$1 \leq n,m,k \leq 5\times10^4$
算法
Part1 O(1)的状态转移
对于上面的例题，我们可以发现从 $[L,R]$ 转移到 $[L,R+1]$ 是 $O(1)$ 的。
我们维护两个指针 $l,r$，并且维护一个 cnt[] 数组来记录当前区间的 $c_i$，在 $r$ 右移一格的时候，加上对应的 $cnt$，然后要维护的 $\sum_{i=1}^kc_i^2$ 也很好转移，计算一下，就会得到
$$s_{l,r+1} = s_{l,r} + 2\times c_{a_{r+1}} + 1$$
同理对于其他三种情况，转移都是 $O(1)$ 的。
所以，假设我们有两个询问 $[L_1, R_1], [L_2, R_2]$，我们在询问完 $[L_1, R_1]$ 后，将左右指针一个个移动到 $[L_2, R_2]$ 似乎就可以节省一点时间了。（如果它们离得比较近的话）
Part2 莫队思路
既然我们可以通过维护两个指针 $l,r$ 来快速转移，我们又事先知道所有的询问（因为询问离线），那有什么办法将这些询问靠近一些，来节省更多时间呢？
分块思想！
我们将区间划分为 $\sqrt n$ 块，然后对于每个询问 $[L_i,R_i]$，我们根据 $L_i$ 的值，把它放进对应的块中。
然后，我们将所有的询问首先根据 所在块的编号 来sort，对于同一块内的询问，根据 $R_i$ 从小到大 来sort。
最后，根据sort的顺序来处理每个询问，询问之间的转移 就按照上面的左右指针移动来处理。这样我们能在 $O(n\sqrt n)$ 时间内处理好每一个区间。
算法步骤
- 预处理所有询问，记录询问的
l,r，记录be（代表l对应是哪个块），记录id（代表原先是第几个询问）。 - 根据
be作为第一关键字，r作为第二关键字进行sort。 - 定义global variable
int l = 1, r = 0, ans = 0。 - 按照sort后的顺序进行询问，调整
l,r指针，并相应更新ans，然后将ans根据id放入答案数组中。
需要注意的点
- 注意在转移过程中，使用的是
--l还是l++。r还有更新ans的时候也类似，要根据具体情况来看。 - 注意初始情况下，
l = 1, r = 0。 be是根据l的位置决定的。
复杂度证明
先注意：
- 同一个块内的 $L_i$ 并没有顺序。
- 同一个块内的 $R_i$ 没有限制，可以横跨整个区间。
左指针在块内移动 的复杂度：注意到，同一个块内的 $L_i$ 并没有顺序，所以每次询问可能有 $O(B)$ 的复杂度（$B$为块的大小）。总复杂度为 $O(mB)$
右指针在块内移动 的复杂度：因为是 $R_i$ 是有序的，所以在同一个块内移动的总复杂度为 $O(n)$
左指针在块之间移动 的复杂度：每次移动复杂度为 $O(2B)$。总复杂度为 $O(\frac{n}{B} * 2B) = O(2n)$
右指针在块之间移动 的复杂度：总共有 $\frac{n}{B}$ 个块，每次在块之间移动没有限制，复杂度为 $O(n)$。总复杂度为 $O(\frac{n^2}{B})$
综上，复杂度为 $O(mB) + O(n) + O(\frac{n^2}{B})$
当我们取 $B = \sqrt n$ 时，复杂度为 $O(n \sqrt n)$
• 实际上最优复杂度应该取 $B = \frac{n}{\sqrt m}$，总复杂度为 $O(n \sqrt m)$
根据操作次数优化莫队
考虑一个问题：
题意
给定一个数组 $a_i$ 和 $q$ 个询问，每次询问 $a_{[L,R]}$ 之间的mex。
其中，$n \leq 10^5$。
如果我们用莫队来做，怎么维护这个 mex 呢？如果用 set 的话会多加一个log，显然不行。
注意到，我们有 $O(n \sqrt n)$ 次修改操作，而只有 $O(n)$ 次询问 mex 的操作。
所以我们不妨让修改变成 $O(1)$，让询问mex变成 $O(\sqrt n)$，这样总复杂度就维持在了 $O(n \sqrt n)$。
我们可以维护一个 cnt[] 数组，表示元素 $i$ 出现了几次。
再根据值域分块，代表一个值域内有多少个元素。询问时，我们从小到大枚举块，当一个块的元素数量未满时，就说明mex在这个块内。
• CF1000F 也可以这么做，虽然那个题的数据范围过不了。
例题
例1 小B的询问
就是上面的例题，这里直接放代码。
代码
using namespace std;
#include <bits/stdc++.h>
#define ll long long
const int maxn = 5e4+5;
const int maxm = 5e4+5;
int n,m,k;
int sz;
int arr[maxn];
ll cnt[maxn];
ll ans[maxn];
struct query {
int l,r,be,id;
} q[maxm];
bool cmp(query& a, query& b) {
if (a.be == b.be) return a.r < b.r;
return a.be < b.be;
}
int l = 1,r = 0;
ll add(int x) {
ll res = 2LL * cnt[arr[x]] + 1LL;
cnt[arr[x]]++;
return res;
}
ll del(int x) {
ll res = -2LL * cnt[arr[x]] + 1LL;
cnt[arr[x]]--;
return res;
}
int main() {
cin >> n >> m >> k;
sz = sqrt(n);
for (int i = 1; i <= n; i++) cin >> arr[i];
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
q[i].be = (q[i].l-1) / sz;
}
sort(q+1, q+m+1, cmp);
ll res = 0;
for (int i = 1; i <= m; i++) {
int ql = q[i].l, qr = q[i].r;
while (r < qr) res += add(++r);
while (r > qr) res += del(r--);
while (l < ql) res += del(l++);
while (l > ql) res += add(--l);
ans[q[i].id] = res;
}
for (int i = 1; i <= m; i++) cout << ans[i] << "\n";
}
例2 小Z的袜子
题意
有 $N$ 个袜子，每个袜子 $i$ 有一个颜色 $c_i$，给定 $M$ 个询问 $[L,R]$，每次询问回答 $[L,R]$ 区间内随机抽两个袜子，颜色相同的概率？
其中 $N,M \leq 50000, c_i \in [1,N]$
题解
维护 分子和分母：
每次区间长度加 $1$：分母增加 $len$（$len$ 为增加前的区间长度），分子增加 $cnt_{c_i}$ （$cnt_{c_i}$ 为新增的颜色 $c_i$ 原来的数量）。
每次区间长度减 $1$：分母减少 $len-1$（$len$ 为减少前的区间长度），分子减少 $cnt_{c_i} - 1$ （$cnt_{c_i}$ 为减少的颜色 $c_i$ 原来的数量）。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 5e4+5;
const int maxm = 5e4+5;
int n,m;
struct query {
int l,r,be,id;
ll nu,de;
} q[maxm];
int arr[maxn];
int cnt[maxn];
bool cmp(query& a, query& b) {
if (a.be == b.be) {
return a.r < b.r;
}
return a.be < b.be;
}
ll nu = 0, de = 0;
ll gcd(ll a, ll b) {
if (!b) return a;
return gcd(b, a%b);
}
int sz;
int main() {
scanf("%d%d",&n,&m);
sz = sqrt(n);
for (int i = 1; i <= n; i++) scanf("%d",&arr[i]);
for (int i = 1; i <= m; i++) {
int l,r; scanf("%d%d",&l,&r);
q[i].id = i;
q[i].be = (l-1)/sz;
q[i].l = l, q[i].r = r;
}
sort(q+1, q+m+1, cmp);
ll l = 1, r = 0;
for (int i = 1; i <= m; i++) {
int ql = q[i].l, qr = q[i].r, id = q[i].id;
if (ql == qr) {
q[id].nu = 0, q[id].de = 1;
continue;
}
while (r < qr) de += (r-l+1), r++, nu += cnt[arr[r]], cnt[arr[r]]++;
while (r > qr) de -= (r-l), nu -= (cnt[arr[r]] - 1), cnt[arr[r]]--, r--;
while (l > ql) de += (r-l+1), l--, nu += cnt[arr[l]], cnt[arr[l]]++;
while (l < ql) de -= (r-l), nu -= (cnt[arr[l]] - 1), cnt[arr[l]]--, l++;
q[id].nu = nu, q[id].de = de;
}
for (int i = 1; i <= m; i++) {
nu = q[i].nu, de = q[i].de;
if (nu == 0) {
printf("0/1\n");
continue;
}
ll g = gcd(nu,de);
nu /= g, de /= g;
printf("%lld/%lld\n",nu,de);
}
}
例3 CF617E
题意
给定 $n$ 个整数 $a_1,a_2,…,a_n$，还有一个整数 $k$ ，以及 $m$ 个询问 $[l,r]$，每次询问求 有多少个$i,j$ 满足：
- $l \leq i \leq j \leq r$
- $a_i \text{ xor } a_{i+1} \text{ xor } … \text{ xor } a_j = k$
其中，$1 \leq n,m \leq 10^5, 0 \leq k \leq 10^6, 0 \leq a_i \leq 10^6$
题解
首先定义一个前缀 $\text{ xor }$ 数组满足 $s_i = a_1 \text{ xor } a_2 \text{ xor } … \text{ xor } a_i$，这样问题转化为：
每次询问求 有多少个$i,j$ 满足：
- $l \leq i \leq j \leq r$
- $s_i \text{ xor } s_j = k$
注意到，$s_j = s_i \text{ xor } k$，所以我们可以维护一个 cnt[] 数组，记录一下当前区间每个元素出现了多少次。
然后，比如在区间扩张的过程中，就检查 cnt[] 中当前元素 cur 出现的次数，给 ans 加上，然后 cnt[cur ^ k]++;
代码
using namespace std;
#include <bits/stdc++.h>
#define ll long long
const int mod = 1e9+7;
const int maxn = 1e5+5;
const int maxm = 1e6+5;
int n,m,k;
struct query {
int l,r,id,be;
} q[maxn];
bool cmp(query a, query b) {
if (a.be == b.be) return a.r < b.r;
return a.be < b.be;
}
int l = 0, r = -1;
int cnt[2*maxm];
int s[maxn];
ll b[maxn];
double start;
ll ans = 0;
void add(int x) {
ans += (ll)cnt[s[x]];
cnt[s[x] ^ k]++;
}
void del(int x) {
cnt[s[x] ^ k]--;
ans -= (ll)cnt[s[x]];
}
void ask(int L, int R) {
while (r < R) add(++r);
while (r > R) del(r--);
while (l < L) del(l++);
while (l > L) add(--l);
}
int main() {
fastio;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) cin >> s[i];
for (int i = 1; i <= n; i++) s[i] ^= s[i-1];
int sz = sqrt(n);
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].l--;
q[i].id = i;
q[i].be = (q[i].l-1)/sz;
}
sort(q+1, q+m+1, cmp);
for (int i = 1; i <= m; i++) {
ask(q[i].l, q[i].r);
b[q[i].id] = ans;
}
for (int i = 1; i <= m; i++) cout << b[i] << "\n";
}
带修莫队
常规的莫队的状态是两个指针 $(l,r)$。带修莫队则增加了一个状态的指针 $t$，代表时间，这样就是 $(l,r,t)$ 作为一个状态了。
转移的时候则可以往 $6$ 个方向转移，每次转移仍然是 $O(1)$ 的。
为什么要带时间呢？我们利用时间来记录修改。每有一次修改，我们就记录这个修改的时间为 ++t，查询不计入时间轴内，但查询本身需要记录它对应的时间点。
然后在回答每一次查询的时候，我们希望把时间轴调整到这个查询所在的时间点，在调整时间的时候就进行/回溯修改。
• 我们记录两种 struct，一种是查询，一种是修改。
而每个查询sort的时候也是有讲究的，第一优先级是 $l$ 所在的block（和原先一样），第二优先级是 $r$ 所在的 block（注意和原先不一样！），第三优先级是时间。
• 块的大小取 $n^{\frac{2}{3}}$，总时间复杂度为 $O(n^{\frac{5}{3}})$。
例1 洛谷P1903 [国家集训队] 数颜色 / 维护队列
题意
给定 $n$ 个元素，每个元素拥有一个颜色 $c_i$。
现在有两种询问，询问共 $m$ 个。
- $Q~L~R$：询问 $[L,R]$ 之间有几种颜色。
- $R~P~C$：将位置 $P$ 的颜色替换为 $C$。
其中，$n,m \leq 10^5$。
题解
上面都说完了，讲一些需要注意的点。
- 查询和修改分开储存，并且 sort 只考虑查询，时间点的增加只考虑修改。
- 块的大小取 $n^{\frac{2}{3}}$。
- 在移动时间点，进行修改的时候，不用区分是修改还是回溯，只要将当前的颜色与询问里的 swap 就行了。因为修改以后，下一次跑到这个时间点肯定是回溯。直接交换就很方便。
- 在移动时间点修改时，要讨论一下这次修改是否在当前查询范围内，在的话才修改答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 133333 + 5;
int n, m, a[maxn];
struct Query {
int l, r, t, id;
} q[maxn];
struct Modify {
int p, c, t; // p: pos, c: color, t: time
} mo[maxn];
int tim = 0; // time for modify
int B, cnt[(int)(1e6+5)];
int ans = 0;
void add(int x) {
int c = a[x];
cnt[c]++;
if (cnt[c] == 1) ans++;
}
void del(int x) {
int c = a[x];
cnt[c]--;
if (cnt[c] == 0) ans--;
}
// 当前的询问 (query) 编号是 i, 要执行的修改是第t个（时间为t）
void modify(int i, int t) {
auto [p,c,_] = mo[t];
auto [L,R,__,id] = q[i];
if (L <= p && R >= p) { // 当前的 count 要更改
del(p); // 删掉这个颜色
cnt[c]++;
if (cnt[c] == 1) ans++; // 加上新颜色
}
swap(a[p], mo[t].c);
}
int res[maxn];
int main() {
fastio;
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
B = pow(n, 0.6666);
int qid = 0;
for (int i = 1; i <= m; i++) {
char c; cin >> c;
if (c == 'Q') {
int l,r; cin >> l >> r;
++qid;
q[qid] = {l, r, tim, qid};
} else {
int p,c; cin >> p >> c;
++tim;
mo[tim] = {p, c, tim};
}
}
sort(q+1, q+qid+1, [](auto a, auto b) {
if (a.l / B == b.l / B) {
if (a.r / B == b.r / B) return a.t < b.t;
return a.r / B < b.r / B;
}
return a.l / B < b.l / B;
});
int l = 1, r = 0, now = 0;
for (int i = 1; i <= qid; i++) {
auto [L, R, t, id] = q[i];
while (l < L) del(l++);
while (l > L) add(--l);
while (r > R) del(r--);
while (r < R) add(++r);
while (now < t) modify(i, ++now);
while (now > t) modify(i, now--);
res[id] = ans;
}
for (int i = 1; i <= qid; i++) cout << res[i] << "\n";
}
例2 CF940F. Machine Learning
题意
给定一个数组 $a_1, a_2, …, a_n$ 和 $q$ 个询问，询问有两种：
第一种询问：每次询问一个区间 $[L,R]$，回答：
令 $c_i$ 为数字 $i$ 在 $[L,R]$ 内出现的次数，求 $\text{mex} \{c_0,c_1,…,c_{10^9}\}$。
第二种询问：给定 $p~x$，将 $a_p$ 改为 $x$。
其中，$1 \leq n,q \leq 10^5, a_i \in [1,10^9]$。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+55;
const int maxm = 4e4+55;
int n, m, a[maxn];
struct Query {
int l, r, t, id;
} q[maxn];
struct Modify {
int p, c, t; // p: pos, c: color, t: time
} mo[maxn];
int tim = 0; // time for modify
int B;
const int M = sqrt(1e5);
struct Mex {
int cnt[maxn]; // cnt[i]: i 出现的次数
int csum[maxn]; // csum[i]: 第i个block里面的元素数量，第0个block: [0, M-1], 第1个block: [M, 2M-1] ...
Mex() {
cnt[0] = 1e9;
csum[0] = 1;
}
// 加入一个数字 x, x <= 1e5
void add(int x) {
if (x > maxn || x < 0) return; // 可能加入了 cnt[0] = 1e9
cnt[x]++;
if (cnt[x] == 1) csum[x / M]++;
}
void del(int x) {
if (x > maxn || x < 0) return;
cnt[x]--;
if (cnt[x] == 0) csum[x / M]--;
}
int mex() {
for (int i = 0; ; i++) {
if (csum[i] != M) {
for (int j = i * M; j <= i * M + M - 1; j++) {
if (!cnt[j]) return j;
}
}
}
return -1;
}
} mex;
int cnt[maxn<<1];
void add(int x) {
int c = a[x];
cnt[c]++;
mex.del(cnt[c] - 1);
mex.add(cnt[c]);
}
void del(int x) {
int c = a[x];
cnt[c]--;
mex.del(cnt[c] + 1);
mex.add(cnt[c]);
}
// 当前的询问 (query) 编号是 i, 要执行的修改是第t个（时间为t）
void modify(int i, int t) {
auto [p,c,_] = mo[t];
auto [L,R,__,id] = q[i];
if (L <= p && R >= p) { // 当前的 count 要更改
del(p); // 删掉这个颜色
cnt[c]++;
mex.del(cnt[c] - 1);
mex.add(cnt[c]);
}
swap(a[p], mo[t].c);
}
map<int, int> mp;
int mid = 0;
int res[maxn];
int main() {
fastio;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
if (!mp.count(a[i])) mp[a[i]] = ++mid;
a[i] = mp[a[i]];
}
B = pow(n, 0.6666);
int qid = 0;
for (int i = 1; i <= m; i++) {
int op; cin >> op;
if (op == 1) {
int l,r; cin >> l >> r;
++qid;
q[qid] = {l, r, tim, qid};
} else {
int p,c; cin >> p >> c;
if (!mp.count(c)) mp[c] = ++mid;
c = mp[c];
++tim;
mo[tim] = {p, c, tim};
}
}
sort(q+1, q+qid+1, [](auto a, auto b) {
if (a.l / B == b.l / B) {
if (a.r / B == b.r / B) return a.t < b.t;
return a.r / B < b.r / B;
}
return a.l / B < b.l / B;
});
int l = 1, r = 0, now = 0;
for (int i = 1; i <= qid; i++) {
auto [L, R, t, id] = q[i];
while (l < L) del(l++);
while (l > L) add(--l);
while (r > R) del(r--);
while (r < R) add(++r);
while (now < t) modify(i, ++now);
while (now > t) modify(i, now--);
res[id] = mex.mex();
}
for (int i = 1; i <= qid; i++) cout << res[i] << "\n";
}