莫队 学习笔记

作者: xht37 分类: 笔记 发布时间: 2020-04-13 12:15

Visits: 473

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。

普通莫队

设定块大小 $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$ 从大到小排序。

注意,排序时需要重载 <,必须符合严格弱序,即:

  1. 非自反性:$x \not< x$。
  2. 非对称性:若 $x < y$,则 $y \not< x$。
  3. 传递性:若 $x < y$,$y < z$,则 $x < z$。
  4. 不可比性的传递性:若 $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;
}

参考资料

发表评论

电子邮件地址不会被公开。 必填项已用*标注