莫队 | DDOSvoid's Blog

简介

这里还没有简介

大概就是用来有点劣的时间复杂度解决一些其他数据结构不能维护的可离线问题

普通莫队

我们只有询问的莫队称为普通莫队

我们将询问按照双关键字排序，第一关键字是左端点所在的块，第二关键字是右端点的大小

我们令块大小为 $S$，不妨假设端点移动的时间复杂度为 $O(1)$，我们尝试分析复杂度

首先是左端点，注意在块内，每次移动为 $O(S)$，块间每次移动同样为 $O(S)$，总的移动就是 $O(mS)$

对于右端点，块内递增，所以总共是 $O(n)$，块间移动为 $O(n)$，总共有 $O(\frac{n}{S})$ 块，总的移动是 $O(\frac{n}{S}n)$

所以总的时间复杂度就是 $O(\frac{n}{S}n+mS)$

如果取 $S=\sqrt n$，时间复杂度为 $O((n+m)\sqrt n)$

如果取 $S=\frac{n}{\sqrt m}$，时间复杂度为 $O(n\sqrt m)$

模板

SP3267 DQUERY - D-query

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 30010
#define maxs 1000010
#define maxm 200010
using namespace std;

int n, m, a[maxn]; 

int blo, ans[maxm]; 
struct Query {
    int l, r, id;

    friend bool operator < (const Query &u, const Query &v) {
        if (u.l / blo == v.l / blo) return u.l / blo & 1 ? u.r < v.r : u.r > v.r;
        return u.l < v.l;
    }
} Q[maxm];

int cnt[maxs], Ans;
inline void add(int v) {
    if (++cnt[v] == 1) ++Ans;
}

inline void del(int v) {
    if (--cnt[v] == 0) --Ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cin >> m; blo = n / sqrt(m); 
    for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i; 
    sort(Q + 1, Q + m + 1);
    int l = Q[1].l, r = l - 1;
    for (int i = 1; i <= m; ++i) {
        while (r < Q[i].r) add(a[++r]);
        while (l > Q[i].l) add(a[--l]);
        while (r > Q[i].r) del(a[r--]);
        while (l < Q[i].l) del(a[l++]);
        ans[Q[i].id] = Ans;
    }
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n"; 
    return 0; 
}

带修莫队

在普通莫队的基础上我们加入了修改，所以我们第一想法就是将莫队变成三维的

我们令块大小为 $O(n^{\frac{2}{3}})$，能否得到时间复杂度为 $O(n^{\frac{5}{3}})$

模板

Luogu P1903 [国家集训队]数颜色 / 维护队列

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 140000
#define maxs 1000010
using namespace std;

int n, m, a[maxn]; 

int c1, c2, blo; 
struct Query {
    int l, r, id, k;

    friend bool operator < (const Query &u, const Query &v) {
        if (u.l / blo != v.l / blo) return u.l < v.l;
        if (u.r / blo != v.r / blo) return u.r < v.r; 
        return u.k < v.k; 
    }
} Q[maxn];

struct Modify {
    int k, v;
} C[maxn];

int ans, cnt[maxs]; 
inline void add(int v) {
    if (++cnt[v] == 1) ++ans;
}

inline void del(int v) {
    if (--cnt[v] == 0) --ans;
}

inline void modify(int i, int l, int r) {
    if (l <= C[i].k && C[i].k <= r) 
        del(a[C[i].k]), add(C[i].v);
    swap(a[C[i].k], C[i].v);
}

int Ans[maxn], cans; 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; blo = pow(n, 0.6666);
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    for (int i = 1; i <= m; ++i) {
        char s[3]; int x, y; cin >> s + 1 >> x >> y;
        if (s[1] == 'Q') Q[++c1] = { x, y, ++cans, c2 };
        else C[++c2] = { x, y }; 
    }
    sort(Q + 1, Q + c1 + 1);
    int l = Q[1].l, r = l - 1, k = 0;
    for (int i = 1; i <= c1; ++i) {
        while (r < Q[i].r) add(a[++r]);
        while (l > Q[i].l) add(a[--l]);
        while (r > Q[i].r) del(a[r--]);
        while (l < Q[i].l) del(a[l++]);
        while (k < Q[i].k) modify(++k, l, r);
        while (k > Q[i].k) modify(k--, l, r);
        Ans[Q[i].id] = ans;
    }
    for (int i = 1; i <= cans; ++i) cout << Ans[i] << "\n"; 
    return 0;
}

树上莫队

我们利用入栈和出栈序，将树上简单路径变成序列

如果 $u$ 是 $v$ 的祖先，那么我们只需统计区间 $in[u]$ 到 $in[v]$ 上出现一次的点的贡献

否则，我们需要统计 $out[u]$ 到 $in[v]$ 上出现一次的点，需要注意到的是，$lca(u.v)$ 的贡献没有统计需要单独计算

模板

SP10707 COT2 - Count on a tree II

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 40010
#define maxm 100010
using namespace std;

int n, m, a[maxn]; 

int b[maxn]; 
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); int cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b;
}

int blo; 
struct Query {
    int l, r, g, id;

    friend bool operator < (const Query &u, const Query &v) {
        if (u.l / blo == v.l / blo) return u.l / blo & 1 ? u.r < v.r : u.r > v.r;
        return u.l < v.l;
    }
} Q[maxm];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn]; 
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int f[maxn][21], dep[maxn], in[maxn], out[maxn], bl[maxn * 2], c2;
void dfs(int u, int fa) {
    in[u] = ++c2; bl[c2] = u; 
    for (int i = head[u]; ~i; i = e[i].next) { 
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; f[v][0] = u; dfs(v, u); 
    } out[u] = ++c2; bl[c2] = u;
}

void init_lca() {
    for (int j = 1; j <= 20; ++j) 
        for (int i = 1; i <= n; ++i)
            f[i][j] = f[f[i][j - 1]][j - 1];
}

int get_lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y); 
    for (int i = 20; ~i; --i)
        if (dep[f[x][i]] >= dep[y]) x = f[x][i];
    if (x == y) return x;
    for (int i = 20; ~i; --i)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    return f[x][0];
}

int cnt[maxn], Ans[maxm], ans; bool use[maxn];
inline void modify(int k) {
    if (!use[k] && ++cnt[a[k]] == 1) ++ans;
    if (use[k] && --cnt[a[k]] == 0) --ans;
    use[k] ^= 1; 
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; blo = sqrt(n); 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i < n; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x);
    } 
    init_hash(); dep[1] = 1; dfs(1, 0); init_lca();
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        if (in[x] > in[y]) swap(x, y);
        if (in[x] <= in[y] && out[y] <= out[x]) 
            Q[i] = { in[x], in[y], 0, i };
        else Q[i] = { out[x], in[y], in[get_lca(x, y)], i }; 
    } sort(Q + 1, Q + m + 1); 
    int l = Q[1].l, r = l - 1;
    for (int i = 1; i <= m; ++i) {
        while (r < Q[i].r) modify(bl[++r]);
        while (l > Q[i].l) modify(bl[--l]);
        while (r > Q[i].r) modify(bl[r--]);
        while (l < Q[i].l) modify(bl[l++]);
        if (Q[i].g) modify(bl[Q[i].g]);
        Ans[Q[i].id] = ans;
        if (Q[i].g) modify(bl[Q[i].g]); 
    }
    for (int i = 1; i <= m; ++i) cout << Ans[i] << "\n"; 
    return 0;
}

回滚莫队

大概就是对于求最值或者其他一些问题，这些问题不支持删除

我们考虑对于左端点同一块内的询问一块处理，左端点暴力重构，右端点递增

然后将两边的贡献合到一起，注意到时间复杂度依然是 $O(\frac{n}{S}n+mS)$

模板

AT1219 歴史の研究

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define maxn 100010
#define ll long long 
using namespace std;

int n, m, k, a[maxn]; 

int b[maxn]; 
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); int cnt = unique(b + 1, b + n + 1) - b - 1; 
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b; 
}

int blo, bl[maxn], R[maxn]; 
struct Query {
    int l, r, k, id;

    friend bool operator < (const Query &u, const Query &v) {
        if (bl[u.l] == bl[v.l]) return u.r < v.r;
        return u.l < v.l;
    }
} Q[maxn];

ll s1[maxn], s2[maxn], Ans[maxn], ans;
inline void add(int v, ll &ans) {
    s1[v] += b[v];
    ans = max(ans, s1[v]); 
}

inline void Add(int v, ll &ans) {
    s2[v] += b[v];
    ans = max(ans, s1[v] + s2[v]); 
} 


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; blo = sqrt(n);
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_hash(); 
    for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
    for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1, R[bl[i]] = bl[i] * blo;
    sort(Q + 1, Q + m + 1);
    for (int o = 1, p = 1; o <= m; o = p) {
        while (bl[Q[o].l] == bl[Q[p].l]) ++p;
        ll ans = 0; int r = R[bl[Q[o].l]], _r = r; fill(s1, s1 + maxn, 0); 
        for (int i = o; i < p; ++i) {
            while (r < Q[i].r) add(a[++r], ans);
            Ans[Q[i].id] = ans;
            for (int j = Q[i].l; j <= min(Q[i].r, _r); ++j) Add(a[j], Ans[Q[i].id]);
            for (int j = Q[i].l; j <= min(Q[i].r, _r); ++j) s2[a[j]] = 0; 
        }
    }
    for (int i = 1; i <= m; ++i) cout << Ans[i] << "\n"; 
    return 0;
}

二次离线莫队

大概就是我们考虑区间从 $[l,r]$ 转移到 $[l,r+1]$ 的增量是什么

容易得到是 $a[r+1]$ 对区间 $[l,r]$ 的贡献，如果贡献满足可减性，那么我们可以拆成 $a[r+1]$ 对 $[1,l-1]$ 和 $[1,r]$ 的贡献

其中 $a[r+1]$ 对 $[1,r]$ 的贡献我们可以考虑预处理，然后就是 $a[r+1]$ 对 $[1,l-1]$ 的贡献，这个东西一共有 $O(n\sqrt n)$ 对

我们考虑离线下来之后利用根号平衡来解决，这样总的时间复杂度就是 $O(n\sqrt n)$，需要注意到空间方面，我们不需要将这 $O(n\sqrt n)$ 对都存下来，每次指针的移动是一个区间，我们可以直接存这个区间，这样空间复杂度可以做到 $O(n)$

模板

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define maxn 100010
#define maxs 340
#define lowbit(i) ((i) & (-i))
#define ll long long
using namespace std;

int n, m, a[maxn];

ll pre[maxn], suf[maxn];

int b[maxn], cnt;
void init_hash() {
    for (int i = 1; i <= n; ++i) b[i] = a[i];
    sort(b + 1, b + n + 1); cnt = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + cnt + 1, a[i]) - b; 
}

int Bit[maxn];
void add(int i, int v) { while (i <= cnt) Bit[i] += v, i += lowbit(i); }

int get_sum(int i) {
    int s = 0;
    while (i) s += Bit[i], i -= lowbit(i);
    return s;
}

int blo;
struct Query {
    int l, r, id;

    friend bool operator < (const Query &u, const Query &v) {
        return u.l / blo == v.l / blo ? u.r < v.r : u.l < v.l;
    }
} Q[maxn];

struct query {
    int l, r, opt, id;
}; vector<query> A[maxn], B[maxn];

struct Block {
    int n, blo, num, l[maxs], r[maxs], bl[maxn], a[maxn], d[maxs];
    void init(int _n) {
        n = _n; blo = sqrt(n); num = (n + blo - 1) / blo;
        for (int i = 1; i <= num; ++i) {
            l[i] = (i - 1) * blo + 1;
            r[i] = i * blo;
        } r[num] = n;
        for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
        for (int i = 1; i <= n; ++i) a[i] = 0;
        for (int i = 1; i <= num; ++i) d[i] = 0; 
    }

    void update(int k, int v) {
        for (int i = k; i <= r[bl[k]]; ++i) a[i] += v;
        for (int i = bl[k] + 1; i <= num; ++i) d[i] += v;
    }

    int query(int k) { return d[bl[k]] + a[k]; } 
} S;

ll ans[maxn];
void solve() {
    S.init(cnt);
    for (int i = 1; i <= n; ++i) {
        S.update(a[i], 1);
        for (auto t : A[i])
            for (int j = t.l; j <= t.r; ++j)
                ans[t.id] += t.opt * (i - S.query(a[j]));
    }
    S.init(cnt);
    for (int i = n; i; --i) {
        S.update(a[i], 1);
        for (auto t : B[i]) 
            for (int j = t.l; j <= t.r; ++j)
                ans[t.id] += t.opt * S.query(a[j] - 1);
    }
}

int main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; blo = sqrt(m);
    for (int i = 1; i <= n; ++i) cin >> a[i]; init_hash();
    for (int i = 1; i <= n; ++i) add(a[i], 1), pre[i] = pre[i - 1] + i - get_sum(a[i]);
    for (int i = 1; i <= cnt; ++i) Bit[i] = 0;
    for (int i = n; i; --i) add(a[i], 1), suf[i] = suf[i + 1] + get_sum(a[i] - 1);
    for (int i = 1; i <= m; ++i) cin >> Q[i].l >> Q[i].r, Q[i].id = i;
    sort(Q + 1, Q + m + 1); int l = Q[1].l, r = l - 1; 
    for (int i = 1; i <= m; ++i) {
        if (r < Q[i].r) {
            ans[Q[i].id] += pre[Q[i].r] - pre[r];
            A[l - 1].push_back({ r + 1, Q[i].r, -1, Q[i].id });
            r = Q[i].r;
        }
        if (l > Q[i].l) {
            ans[Q[i].id] += suf[Q[i].l] - suf[l];
            B[r + 1].push_back({ Q[i].l, l - 1, -1, Q[i].id });
            l = Q[i].l;
        }
        if (r > Q[i].r) {
            ans[Q[i].id] -= pre[r] - pre[Q[i].r];
            A[l - 1].push_back({ Q[i].r + 1, r, 1, Q[i].id });
            r = Q[i].r;
        }
        if (l < Q[i].l) {
            ans[Q[i].id] -= suf[l] - suf[Q[i].l];
            B[r + 1].push_back({ l, Q[i].l - 1, 1, Q[i].id });
            l = Q[i].l;
        }
    } solve();
    for (int i = 1; i <= m; ++i) ans[Q[i].id] += ans[Q[i - 1].id]; 
    for (int i = 1; i <= m; ++i) cout << ans[i] << "\n";
    return 0;
}

技巧

我们注意到在莫队中，查询 $O(n)$，而端点的移动是 $O(n\sqrt n)$ 的

所以在查询的时候我们最大允许的复杂度是 $O(\sqrt n)$，这也使得我们可以利用类似于根号平衡的方法来解决问题

例题

求给定区间内所以异或和为 $k$ 的子区间个数

Luogu P4462 [CQOI2018]异或序列
每次询问两个区间中相同的数出现次数的乘积的和

Luogu P5268 [SNOI2017]一个简单的询问
每次查询一个区间中的属于某个范围的数的个数

Luogu P4396 [AHOI2013]作业
每次查询一个区间中 $k$ 个数字的出现次数的最大值减最小值的最小值

CF 1476G Minimum Difference