莫队学习笔记
stripe_python
·
2024-07-23 18:24:24
·
算法·理论
膜拜给本蒟蒻讲莫队的大佬。
普通莫队
原理
可行条件
离线
步骤
把原数组 a 分成 \sqrt{n} 块。
把询问离线，以 l 所在块为第一关键字、r 所在块为第二关键字排序。遍历询问从上一个暴力更新到下一个。
int m = q.size();
vector<T> res(m);
T ans = 0;
for (int i = 0, l = 1, r = 0; i < m; i++) {
while (l > q[i].l) add(--l, ans);
while (r < q[i].r) add(++r, ans);
while (l < q[i].l) del(l++, ans);
while (r > q[i].r) del(r--, ans);
res[q[i].id] = ans;
}正确性显然，主要是复杂度。
结论：n,q 同阶，取块长 \sqrt{n} 时，复杂度为 O(n\sqrt{n}+q \log q) 。
### 复杂度证明
排序显然为 $O(q \log q)$。
对于 $l$ 的移动：下一个询问与 $l$ 所在块不同时，$d_{\max}=2\sqrt{n}$。
对于 $r$ 的移动：记 $i$ 所属的块为 $b_i$。若 $b_r \ne b_{r'}$ 退化为暴力，复杂度 $O(n)$。同块 $b_i$ 相同，此时排序使用第二关键字 $r$，由于 $r$ 单增，故 $r$ 的移动次数是 $O(n)$ 的。共有 $\dfrac{n}{\sqrt{n}}=\sqrt{n}$ 个块，所以 $r$ 的移动是 $O(n\sqrt{n})$ 的。
$O(\dfrac{n^2}{m}+mq)$ 的证明类似。
### 优化
#### 块长优化
当 $q$ 远大于 $n$ 时，需要使 $\dfrac{n^2}{m}+mq$ 最小，此时取块长 $m=\dfrac{n}{\sqrt{q}}$。
#### 奇偶排序优化
从证明中可知，$r$ 的移动是很慢的。
对于属于奇数块的询问，$r$ 按从小到大排序，对于属于偶数块的排序，$r$ 从大到小排序。
这样 $r$ 先处理奇数再处理偶数，是有效的常数优化。
### 代码模板
```cpp
template <class T>
class MBlock {
private:
int unit;
struct node {
int l, r, id;
node() : l(0), r(0), id(0) {}
node(int a, int b, int c) : l(a), r(b), id(c) {}
};
public:
vector<node> q;
explicit MBlock(int u) : unit(u) {}
void add_query(int l, int r, int id) {q.emplace_back(l, r, id);}
vector<T> get(const function<void(int, T&)>& add, const function<void(int, T&)>& del,
const function<void(T&, int)>& get = [](T&, int){}) {
sort(q.begin(), q.end(), [&](const node& x, const node& y) -> bool {
if (x.l / unit != y.l / unit) return x.l < y.l;
if ((x.l / unit) & 1) return x.r < y.r;
return x.r > y.r;
});
int m = q.size();
vector<T> res(m);
T ans = 0;
for (int i = 0, l = 1, r = 0; i < m; i++) {
while (l > q[i].l) add(--l, ans);
while (r < q[i].r) add(++r, ans);
while (l < q[i].l) del(l++, ans);
while (r > q[i].r) del(r--, ans);
get(ans, q[i].id), res[q[i].id] = ans;
}
return res;
}
};
```
## 例题
### [P2709 小B的询问](https://www.luogu.com.cn/problem/P2709)
莫队板子之一。代码如下：
```cpp
int n, q, k, l, r, a[N], cnt[N];
void _main() {
read(n, q, k);
read(a + 1, a + n + 1);
MBlock<int> mblock(sqrt(n));
for (int i = 0; i < q; i++) {
read(l, r);
mblock.add_query(l, r, i);
}
vector<int> res = mblock.get(
[&](int pos, int& t) -> void {
t += 2 * cnt[a[pos]] + 1;
cnt[a[pos]]++;
},
[&](int pos, int& t) -> void {
t -= 2 * cnt[a[pos]] - 1;
cnt[a[pos]]--;
}
);
for (int i : res) writeln(i);
}
```
### [P1494 [国家集训队] 小 Z 的袜子](https://www.luogu.com.cn/problem/P1494)
首先你需要特判 $l=r$，修改一下 `get` 函数即可。
然后令区间内 $i$ 中颜色的数量为 $a_i$，则分子贡献为 $\dfrac{1}{2}a_i(a_i+1)$，分母是 $\dfrac{1}{2}(r-l+1)(r-l)$，然后直接输出即可。
```cpp
int n, q, l, r, a[N], cnt[N], ll[N], rr[N];
void _main() {
read(n, q);
read(a + 1, a + n + 1);
MBlock<int> mblock(sqrt(n));
for (int i = 0; i < q; i++) {
read(l, r);
mblock.add_query(l, r, i);
}
mblock.init();
vector<int> res = mblock.get(
[&](int pos, int& t) -> void {t += cnt[a[pos]]++;},
[&](int pos, int& t) -> void {t -= --cnt[a[pos]];}
);
for (int i = 0; i < q; i++) {
ll[mblock.q[i].id] = mblock.q[i].l;
rr[mblock.q[i].id] = mblock.q[i].r;
}
for (int i = 0; i < q; i++) {
if (res[i] == 0) write(0), putchar('/'), writeln(1);
else {
int t = (rr[i] - ll[i] + 1) * (rr[i] - ll[i]) / 2;
int g = __gcd(res[i], t);
write(res[i] / g), putchar('/'), writeln(t / g);
}
}
}
```
### [P4137 Rmq Problem / mex](https://www.luogu.com.cn/problem/P4137)
其实这题应该放在回滚莫队里，但是 bitset 优化就冲过去了……
`del` 是平凡的，对于 `add`，用一个 `bitset` 压位存储下一个数字是否出现，暴力找即可。复杂度为 $O(n\sqrt{n}+\dfrac{qV}{w})$，其中 $V$ 为值域，$w=64$。开 O2 即可冲过。
```cpp
int n, q, a[N], l, r, cnt[N];
bitset<N> bs;
void add(int x, int& res) {
cnt[a[x]]++, bs[a[x]] = 0;
if (res == a[x]) res = bs._Find_next(a[x]);
}
void del(int x, int& res) {
if (--cnt[a[x]] == 0) {
bs[a[x]] = 1;
res = min(res, a[x]);
}
}
```
### [P4462 [CQOI2018] 异或序列](https://www.luogu.com.cn/problem/P4462) / [CF617E XOR and Favorite Number](https://www.luogu.com.cn/problem/CF617E)。
先处理出来前缀异或 $pre$。由 $pre_i \bigoplus k=pre_j$ 得 $pre_i =pre_j\bigoplus k$，所以开个桶记录一下更新即可。
由于前缀异或的式子是 $pre_j \bigoplus pre_{i-1}$，所以左端点要减一。
```cpp
#define int long long
int n, q, k, a[N], pre[N], cnt[N], l, r;
void _main() {
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> a[i], pre[i] = pre[i - 1] ^ a[i];
MBlock<int> mblock(sqrt(n));
for (int i = 0; i < q; i++) {
cin >> l >> r;
mblock.add_query(l - 1, r, i);
}
vector<int> res = mblock.get(
[&](int x, int& res) -> void {
res += cnt[pre[x] ^ k];
cnt[pre[x]]++;
},
[&](int x, int& res) -> void {
cnt[pre[x]]--;
res -= cnt[pre[x] ^ k];
}
);
for (int i : res) cout << i << '\n';
}
```
### [P3709 大爷的字符串题](https://www.luogu.com.cn/problem/P3709)
题意翻译：查询 $[l,r]$ 区间的众数的出现次数的相反数。
出现次数开通维护即可，众数开桶の桶维护。
但是本蒟蒻懒得离散化，使用 `cc_hash_table` 吸着氧气 920ms 水过。
```cpp
#include <bits/extc++.h>
using namespace __gnu_pbds;
int n, q, a[N], l, r, num[N];
cc_hash_table<int, int> cnt;
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
MBlock<int> mblock(sqrt(n));
for (int i = 0; i < q; i++) {
cin >> l >> r;
mblock.add_query(l, r, i);
}
vector<int> res = mblock.get(
[&](int x, int& res) -> void {
num[cnt[a[x]]]--, num[++cnt[a[x]]]++;
res = max(res, cnt[a[x]]);
},
[&](int x, int& res) -> void {
num[cnt[a[x]]]--;
if (cnt[a[x]] == res && !num[cnt[a[x]]]) res--;
num[--cnt[a[x]]]++;
}
);
for (int i : res) cout << -i << '\n';
}
```
# 带修莫队
## 原理
### 可行条件
这里我们记 $t$ 为这次查询之前做了多少次修改。
1. 离线
2. $[l,r,t]$ 的答案可以以较低复杂度转移到 $[l-1,r,t],[l+1,r,t],[l,r-1,t],[l,r+1,t],[l,r,t-1],[l,r,t+1]$。
### 步骤
把数组分成 $O(n ^{\frac{1}{3}})$ 块，块长 $O(n ^{\frac{2}{3}})$。
> 注：最优块长应当是 $O(\dfrac{n ^{\frac{2}{3}} t^ {\frac{1}{3}}}{q ^{\frac{2}{3}}})$。证明见 [OI-Wiki](https://oi-wiki.org/misc/modifiable-mo-algo/)。实际应用中，一般取 $O(n ^{\frac{2}{3}})$。
类似普通莫队地，坐标除了 $l,r$ 的移动，在时间轴 $t$ 上也作移动。
认为 $n,q,t$ 同级，可以得出，复杂度为 $O(n^{\frac{5}{3}})$，相比于暴力 $O(n^2)$ 还是有很大优化的。
### 代码模板
相较于普通莫队，这里新增了 `upd` 函数。
```cpp
template <class T>
class MBlock {
private:
int unit, time;
struct node {
int l, r, t, id;
node() : l(0), r(0), t(0), id(0) {}
node(int a, int b, int c, int d) : l(a), r(b), t(c), id(d) {}
};
struct change {
int l; T v;
change() : l(0), v(0) {}
change(int a, const T& b) : l(a), v(b) {}
};
public:
vector<node> qq; vector<change> qr;
explicit MBlock(int u) : unit(u), time(0) {}
void add_query(int l, int r, int id) {qq.emplace_back(l, r, time, id);}
void add_change(int l, const T& v) {time++, qr.emplace_back(l, v);}
vector<T> get(const function<void(int, T&)>& add,
const function<void(int, T&)>& del,
const function<void(int, int, T&)>& upd,
const function<void(T&, int)>& get = [](T&, int){}) {
sort(qq.begin(), qq.end(), [&](const node& x, const node& y) -> bool {
if (x.l / unit == y.l / unit) {
if (x.r / unit == y.r / unit) return x.t < y.t;
return x.r < y.r;
}
return x.l < y.l;
});
int m = qq.size();
vector<T> res(m);
T ans = 0;
for (int i = 0, l = 1, r = 0, t = 0; i < m; i++) {
while (l > qq[i].l) add(--l, ans);
while (r < qq[i].r) add(++r, ans);
while (l < qq[i].l) del(l++, ans);
while (r > qq[i].r) del(r--, ans);
while (t < qq[i].t) upd(i, t++, ans);
while (t > qq[i].t) upd(i, --t, ans);
get(ans, qq[i].id), res[qq[i].id] = ans;
}
return res;
}
};
```
## 例题
### [P1903 [国家集训队] 数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903)
这题是带修莫队的板子。这里说明一个块长优化，见[这篇讨论](https://lglg.top/802858)。本题应用中可以取块长为 $1.7 n^{0.667}$，实测自己的板子换了块长后快了 2s。
```cpp
int n, q, a[N], cnt[N], l, r; char opt;
void add(int x, int& res) {
if (++cnt[a[x]] == 1) res++;
}
void del(int x, int& res) {
if (--cnt[a[x]] == 0) res--;
}
void _main() {
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
MBlock<int> mblock(1.7 * pow(n, 0.667));
int id = 0;
for (int i = 0; i < q; i++) {
cin >> opt >> l >> r;
if (opt == 'Q') mblock.add_query(l, r, id), id++;
else mblock.add_change(l, r);
}
vector<int> res = mblock.get(
#define qq mblock.qq
#define qr mblock.qr
add, del, [&](int x, int t, int &res) -> void {
if (qq[x].l <= qr[t].l && qr[t].l <= qq[x].r) { // 被区间包含
del(qr[t].l, res); // 删除端点原值
if (++cnt[qr[t].v] == 1) res++; // 加入修改值
}
swap(a[qr[t].l], qr[t].v);
}
#undef qq
#undef qr
);
for (int i : res) cout << i << '\n';
}
```
# 回滚莫队
## 原理
### 可行条件
1. 离线
2. $[l,r]$ 的答案可以以较低复杂度转移到 $[l-1,r],[l,r+1]$ 或者 $[l+1,r],[l,r-1]$。
### 步骤
很多时候 `add` 和 `del` 中有一个无法顺利进行。此时使用回滚莫队。下面先介绍不删除莫队。
仍然分块并将询问排序。按顺序处理第 $i$ 个询问：
- 若左端点所属块 $B_{l_i} \ne B_{l_{i-1}}$，此时将左右端点初始化为 $l'=B_{l_i}+1,r'=B_{l_i}$。
- 若 $B_{l_i}=B_{r_i}$，暴力扫描区间即可，复杂度 $O(\sqrt{n})$。
- 反之，不断 `add` 直到 $l_i=l',r_i=r'$，回答询问，随后撤销左端点的 `add`，即为回滚。
复杂度证明类似，考虑 $r'$ 单调递增，$l'$ 的移动 $\le \sqrt{n}$，认为 $n,q$ 同阶复杂度为 $O(n\sqrt{n})$。
## 例题
被吃了。
# 二维莫队
被吃了。