莫队 学习笔记
Visits: 537
莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。
普通莫队
设定块大小 $T$,将 $m$ 个询问 $[l,r]$ 离线下来,以 $(\lfloor \frac lT \rfloor, r)$ 为关键字排序后,依次处理每个询问。
时间复杂度:
若 $|l – l^\prime| + |r – r^\prime| = 1$,从 $[l,r]$ 转移到 $[l^\prime, r^\prime]$ 的复杂度是 $\mathcal O(1)$ 的。
整个过程中,$l$ 移动的总次数为 $\mathcal O(mT)$,$r$ 移动的总次数为 $\mathcal O(\frac {n^2}T)$。
取 $T = \frac {n}{\sqrt m}$ 时得到最优复杂度 $\mathcal O(n \sqrt m)$,总时间复杂度 $\mathcal O(m \log m + n \sqrt m)$。
注意,在 $n,m$ 同阶时,取 $T = \sqrt n$ 有最优复杂度 $\mathcal O(n \sqrt n)$,$1\text{s}$ 内最高可以通过 $n \le 2 \times 10^5$ 的题目。但有些毒瘤题目会把数据范围出到 $n \le 5 \times 10^4$,$m \le 10^6$,所以需要稍微注意一下 $n,m$ 不同阶的情况。
常数优化:
考虑奇偶化排序:对于 $\lfloor \frac lT \rfloor$ 为奇数的块,$r$ 从小到大排序;对于 $\lfloor \frac lT \rfloor$ 为偶数的块,$r$ 从大到小排序。
注意,排序时需要重载 <
,必须符合严格弱序,即:
- 非自反性:$x \not< x$。
- 非对称性:若 $x < y$,则 $y \not< x$。
- 传递性:若 $x < y$,$y < z$,则 $x < z$。
- 不可比性的传递性:若 $x \not< y$,$y \not< x$,$y \not< z$,$z \not< y$,则 $x \not< z$,$z \not< x$。
简单来讲就是 $x < y$ 和 $y < x$ 不能同时为真。
【模板】小 Z 的袜子
const int N = 5e4 + 7;
int n, m, T, a[N], c[N];
ll ans[N], sum[N], now;
struct Q {
int l, r, x, y, i;
inline Q() {}
inline Q(int l, int r, int i) : l(l), r(r), i(i) { x = l / T, y = r; }
inline friend bool operator < (const Q &a, const Q &b) {
return a.x == b.x ? (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
}
} q[N];
inline void work(int x, int k) {
x = a[x], now += k > 0 ? c[x] : 1 - c[x], c[x] += k;
}
int main() {
rd(n, m), T = n / sqrt(m), rda(a, n);
for (int i = 1, l, r; i <= m; i++) rd(l, r), q[i] = Q(l, r, i);
sort(q + 1, q + m + 1);
for (int i = 1, l = 1, r = 0; i <= m; i++) {
while (l > q[i].l) work(--l, 1);
while (r < q[i].r) work(++r, 1);
while (l < q[i].l) work(l++, -1);
while (r > q[i].r) work(r--, -1);
ans[q[i].i] = now;
sum[q[i].i] = 1ll * (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2;
}
for (int i = 1; i <= m; i++) {
if (!sum[i]) {
prints("0/1");
continue;
}
ll d = __gcd(ans[i], sum[i]);
print(ans[i] / d, '/'), print(sum[i] / d);
}
return 0;
}
带修莫队
增加一维时间轴,即每次询问变成 $[l,r,t]$。
依然设定块大小 $T$,然后以 $(\lfloor \frac lT \rfloor, \lfloor \frac rT \rfloor,t)$ 为关键字排序,依次处理每个询问。
时间复杂度:
若 $|l – l^\prime| + |r – r^\prime| + |t – t^\prime| = 1$,从 $[l,r,t]$ 转移到 $[l^\prime, r^\prime, t^\prime]$ 的复杂度是 $\mathcal O(1)$ 的。
整个过程中,$l$ 移动的总次数为 $\mathcal O(mT)$,$r$ 移动的总次数为 $\mathcal O(mT+ \frac {n^2}T)$,$t$ 移动的总次数为 $\mathcal O(\frac{n^2m}{T^2})$。
设 $n,m$ 同阶,取 $T = n^{\frac 23}$ 时得到最优复杂度 $\mathcal O(n^{\frac 53})$,$1\text{s}$ 内最高可以通过 $n \le 6 \times 10^4$ 的题目。
那如果 $n,m$ 不同阶咋办?相信我,暴力能过。
【模板】数颜色
const int N = 133337, M = 1e6 + 7;
int n, m, k, T, a[N], c[M], u[N], v[N], ans[N], now;
struct Q {
int l, r, t, x, y, z, i;
inline Q() {}
inline Q(int l, int r, int t, int i) : l(l), r(r), t(t), i(i) { x = l / T, y = r / T, z = t; }
inline friend bool operator < (const Q &a, const Q &b) {
return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.z < b.z : a.z > b.z : (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
}
} q[N];
inline void work(int x, int k) {
now += k > 0 ? !c[x] : -!(c[x] - 1), c[x] += k;
}
inline void update(int i, int x) {
if (q[i].l <= u[x] && u[x] <= q[i].r) work(a[u[x]], -1), work(v[x], 1);
swap(a[u[x]], v[x]);
}
int main() {
rd(n, m), T = pow(n, 2.0 / 3.0), rda(a, n);
for (int i = 1, l, r, t = 0; i <= m; i++) {
char o;
rdc(o);
if (o == 'Q') rd(l, r), ++k, q[k] = Q(l, r, t, k);
else ++t, rd(u[t], v[t]);
}
sort(q + 1, q + k + 1);
for (int i = 1, l = 1, r = 0, t = 0; i <= k; i++) {
while (l > q[i].l) work(a[--l], 1);
while (r < q[i].r) work(a[++r], 1);
while (l < q[i].l) work(a[l++], -1);
while (r > q[i].r) work(a[r--], -1);
while (t < q[i].t) update(i, ++t);
while (t > q[i].t) update(i, t--);
ans[q[i].i] = now;
}
for (int i = 1; i <= k; i++) print(ans[i]);
return 0;
}
回滚莫队
当删除不太容易时,可以考虑回滚莫队。
首先依然分块,对于左右两端点在同一块的询问直接暴力求答案。
其余的询问先像之前那样排序。对于相邻两块,若左端点在同一块,则右端点显然是递增的。每次处理询问时,钦定初始的左端点为当前块下一块的开头,然后先移动右端点,记录下答案后再移动左端点,询问完后还原记录下的答案。
若左端点不在同一块,则直接清空答案。这样做时间复杂度依然是 $\mathcal O(m \log m + n \sqrt m)$ 的。
【模板】历史研究
const int N = 1e5 + 7;
int n, m, T, a[N];
unordered_map<int, int> c;
ll ans[N], now;
struct Q {
int l, r, x, y, i;
inline Q() {}
inline Q(int l, int r, int i) : l(l), r(r), i(i) { x = l / T, y = r; }
inline friend bool operator < (const Q &a, const Q &b) {
return a.x == b.x ? a.y < b.y : a.x < b.x;
}
} q[N];
vi p;
inline void work(int x) {
now = max(now, 1ll * x * (++c[x]));
}
int main() {
rd(n, m), T = n / sqrt(m), rda(a, n);
for (int i = 1, l, r; i <= m; i++) rd(l, r), q[i] = Q(l, r, i);
sort(q + 1, q + m + 1);
for (int i = 1, l, r; i <= m; i++) {
if (i == 1 || q[i].x != q[i-1].x)
l = (q[i].x + 1) * T, r = l - 1, now = 0, c.clear();
if (q[i].x == q[i].r / T) {
for (int j = q[i].l; j <= q[i].r; j++) work(a[j]);
ans[q[i].i] = now;
now = 0, c.clear();
continue;
}
while (r < q[i].r) work(a[++r]);
ll cur = now;
while (l > q[i].l) work(a[--l]), p.pb(a[l]);
ans[q[i].i] = now;
l = (q[i].x + 1) * T, now = cur;
while (p.size()) --c[p.back()], p.pop_back();
}
for (int i = 1; i <= m; i++) print(ans[i]);
return 0;
}
树上莫队
首先要说明的是,树上莫队其实有两种。一种是采用王室联邦中的分块方式对树进行树分块;另一种是将树压成括号序,然后用普通/带修莫队去做。
后者与前者相比,应用上并没有什么劣势,但比前者简单许多,因此本文中只介绍后者。
树上莫队其实就是把树压成一个序列,然后用序列上莫队的方式做就好了。
那么压成什么样的序列可以符合我们的要求呢?
首先想到的肯定是 dfs 序,但压成 dfs 序之后只能处理对于子树的询问。
对于路径的询问,我们就要考虑括号序(欧拉序)了。
括号序其实就是在进入和回溯一个点时都把这个点的编号标记下来,这样可以得到一个长度为 $2n$ 的序列,同时记录点 $i$ 进入和回溯时的时间戳 $in_i, out_i$。
对于一次询问 $(x,y)$,不妨设 $in_x < in_y$。如果 $y$ 在 $x$ 的子树内,则直接询问括号序上的区间 $[in_x,in_y]$,否则询问 $[out_x,in_y]$。对于一次询问 $[l,r]$,其答案为区间中所有只出现了一次的节点对应的答案。另外,对于 $y$ 不在 $x$ 子树内的情况,$\text{LCA}(x,y)$ 并不在 $[out_x,in_y]$ 中,需要单独计算贡献。
找到哪些位置上的节点只出现了一次可以用简单的异或实现。
【模板】糖果公园
const int N = 1e5 + 7;
int n, m, cq, T, k, a[N], c[N], tx[N], ty[N];
ll v[N], w[N], ans[N], now;
vi e[N];
struct Q {
int l, r, t, x, y, z, i, o;
inline Q() {}
inline Q(int l, int r, int t, int i, int o = 0) : l(l), r(r), t(t), i(i), o(o) { x = l / T, y = r / T, z = t; }
inline friend bool operator < (const Q &a, const Q &b) {
return a.x == b.x ? a.y == b.y ? (a.y & 1) ? a.z < b.z : a.z > b.z : (a.x & 1) ? a.y < b.y : a.y > b.y : a.x < b.x;
}
} q[N];
namespace HLD {
int d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
void dfs(int x) {
s[x] = 1;
for (int y : e[x])
if (y != f[x]) {
f[y] = x, d[y] = d[x] + 1;
dfs(y), s[x] += s[y];
if (s[y] > s[son[x]]) son[x] = y;
}
}
void dfs(int x, int p) {
dfn[x] = ++num, rnk[num] = x;
top[x] = p;
if (son[x]) dfs(son[x], p);
for (int y : e[x])
if (y != f[x] && y != son[x])
dfs(y, y);
}
inline int lca(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
x = f[top[x]];
}
return d[x] < d[y] ? x : y;
}
inline void main() {
d[1] = 1, dfs(1), dfs(1, 1);
}
}
using HLD::s;
using HLD::dfn;
using HLD::lca;
using HLD::son;
int in[N], out[N], p[N<<1], r[N<<1], num;
void dfs(int x, int f) {
in[x] = ++num, p[num] = x;
if (son[x]) dfs(son[x], x);
for (int y : e[x])
if (y != f && y != son[x]) dfs(y, x);
out[x] = ++num, p[num] = x;
}
inline void work(int x) {
if (r[x]) now -= v[a[x]] * w[c[a[x]]--], r[x] = 0;
else now += v[a[x]] * w[++c[a[x]]], r[x] = 1;
}
inline void update(int i, int x) {
if (q[i].l <= in[tx[x]] && in[tx[x]] <= q[i].r) work(tx[x]);
if (q[i].l <= out[tx[x]] && out[tx[x]] <= q[i].r) work(tx[x]);
swap(a[tx[x]], ty[x]);
if (q[i].l <= in[tx[x]] && in[tx[x]] <= q[i].r) work(tx[x]);
if (q[i].l <= out[tx[x]] && out[tx[x]] <= q[i].r) work(tx[x]);
}
int main() {
rd(n, m, cq), T = pow(n, 2.0 / 3.0), rda(v, m), rda(w, n);
for (int i = 1, x, y; i < n; i++) rd(x, y), e[x].pb(y), e[y].pb(x);
rda(a, n);
HLD::main();
dfs(1, 0);
for (int i = 1, o, x, y, t = 0; i <= cq; i++) {
rd(o, x, y);
if (o) {
++k;
if (dfn[x] > dfn[y]) swap(x, y);
if (dfn[y] < dfn[x] + s[x]) q[k] = Q(in[x], in[y], t, k);
else q[k] = Q(out[x], in[y], t, k, 1);
} else tx[++t] = x, ty[t] = y;
}
sort(q + 1, q + k + 1);
for (int i = 1, l = 1, r = 0, t = 0; i <= k; i++) {
while (l > q[i].l) work(p[--l]);
while (r < q[i].r) work(p[++r]);
while (l < q[i].l) work(p[l++]);
while (r > q[i].r) work(p[r--]);
while (t < q[i].t) update(i, ++t);
while (t > q[i].t) update(i, t--);
if (q[i].o) work(lca(p[l], p[r]));
ans[q[i].i] = now;
if (q[i].o) work(lca(p[l], p[r]));
}
for (int i = 1; i <= k; i++) print(ans[i]);
return 0;
}
参考资料
- OI Wiki 莫队算法
- Sengxian 莫队算法学习笔记
- ouuan 莫队、带修莫队、树上莫队详解