莫队

· · 算法·理论

莫队那些的，比如莫队二离、回滚、带修的都会吧，会那不讲了

我：？？？

莫队

莫涛队长（\times）莫比乌斯队列（\surd）

莫队可以解决一类离线静态区间询问问题，如果可以 O(1) 的将 [l, r] 扩展到 [l, r + 1], [l, r - 1], [l + 1, r], [l - 1, r]，那么便可以用 O(n\sqrt{m}) 的复杂度解决

那么作法就显然了，先离线排序，然后暴力的一步一步挪动询问区间来获取答案，而排序就以 l 所在块为第一关键字，r 为第二关键字从小到大排序即可，块长取 \frac{n}{\sqrt{m}} 即可

复杂度证明参见 OI-wiki（

奇偶化排序

有数据：

1 1
2 10000
3 1
4 10000

按照上面的做法会多跳很多遍，于是便有了奇偶化排序，对于属于奇数块的询问，r 按从小到大排序，对于属于偶数块的排序，r 从大到小排序，这样可以使程序变快 30%

例题

[国家集训队] 小 Z 的袜子

区间数颜色，莫队经典题型

code：

#include <bits/stdc++.h>
#define int long long
using namespace std;

constexpr int maxn = 50005;
int n, m, sz, sum;
int c[maxn], cnt[maxn], ans1[maxn], ans2[maxn];
struct query {
    int l, r, id;
    bool operator < (const query &x) const {
        if (l / sz != x.l / sz) return l < x.l;
        return (l / sz) & 1 ? r < x.r : r > x.r; // 奇偶化排序
    }
} a[maxn];
void add(int i) {
    sum += cnt[i];
    cnt[i]++;
}
void del(int i) {
    cnt[i]--;
    sum -= cnt[i];
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    sz = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= m; i++) cin >> a[i].l >> a[i].r, a[i].id = i;
    sort(a + 1, a + m + 1);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++) {
        if (a[i].l == a[i].r) { // 特判
            ans1[a[i].id] = 0, ans2[a[i].id] = 1;
            continue;
        }
        // 区间转移
        // 注意这个顺序
        while (l > a[i].l) add(c[--l]);
        while (r < a[i].r) add(c[++r]);
        while (l < a[i].l) del(c[l++]);
        while (r > a[i].r) del(c[r--]);
        ans1[a[i].id] = sum;
        ans2[a[i].id] = (int)(r - l + 1) * (r - l) / 2;
    }
    for (int i = 1; i <= m; i++) {
        if (ans1[i] != 0) {
            int g = gcd(ans1[i], ans2[i]);
            ans1[i] /= g, ans2[i] /= g;
        } 
        else ans2[i] = 1;
        cout << ans1[i] << '/' << ans2[i] << '\n';
    }
    return 0;
}

这个 l, r 的转移顺序不是固定的，目前看来你只要保持 --l 在 l++ 前，++r 在 r-- 前就是对的，玄学

带修

很明显普通莫队无法支持修改，但有些人就是药用莫队维护动态序列，这个时候就要用到带修改莫队解决

具体怎么做呢，只需要再加入一个时间维 t 就行，排序呢只需要把第二关键字改成 r 所在块，第三关键字改成 t 即可

那么怎么维护扩大缩小区间时的修改呢，假设原来 p 位上的颜色是 a，如果 p 在 [l, r] 内，那么相当于删掉 a，加上 c，并且将原数组的第 p 位修改为 c，不在的话就直接将原数组的第 p 位修改为 c，而如果是去掉这个操作只需要交换 a, c 就行

还有一个问题，这个情况下块长再取 \sqrt{n} 的话复杂度是劣的，而经过分析 n, m, t 同阶时块长取 n^{2/3} 时是最优的，复杂度是 O(n^{\frac{5}{3}})，证明见 OI-wiki（

例题

[国家集训队] 数颜色

模板题，直接做

code：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 150000;
int n, m, block, sum;
int a[maxn], cnt[maxn * 10], pos[maxn], ans[maxn];
struct query {
    int l, r, t, id;
    bool operator < (const query &x) const {
        if (pos[l] != pos[x.l]) return l < x.l;
        if (pos[r] != pos[x.r]) return r < x.r;
        return t < x.t;
    }
} q[maxn]; int qn;
struct update {
    int p, x;
} u[maxn]; int un;
void add(int i) {
    sum += (!cnt[i]); 
    cnt[i]++;
}
void del(int i) {
    cnt[i]--; 
    sum -= (!cnt[i]); 
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    block = pow(n, 2.0 / 3.0);
    for (int i = 1; i <= n; i++) cin >> a[i], pos[i] = i / block;
    for (int i = 1; i <= m; i++) {
        char op;
        int x, y;
        cin >> op >> x >> y;
        if (op == 'Q') q[++qn] = {x, y, un, qn};
        else u[++un] = {x, y};
    }
    sort(q + 1, q + qn + 1);
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= qn; i++) {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        while (t < q[i].t) {
            t++;
            if (u[t].p >= l && u[t].p <= r) add(u[t].x), del(a[u[t].p]);
            swap(a[u[t].p], u[t].x); // 这里不能直接赋值，因为将来要撤回
        }
        while (t > q[i].t) {
            if (u[t].p >= l && u[t].p <= r) add(u[t].x), del(a[u[t].p]);
            swap(a[u[t].p], u[t].x);
            t--;
        }
        ans[q[i].id] = sum;
    }
    for (int i = 1; i <= qn; i++) cout << ans[i] << endl;
    return 0;
}

回滚

有的时候如果只有向外扩展可以实现或者只有向内扩展可以实现，这个时候就可以用回滚莫队快速解决

回滚莫队一般有不删除和不增加两种形式，不过不删除的更常见

例题

[JOISC 2014] 历史的研究 / Historical Research

这道题就是典型的删除做不了的，首先排序还是一样的，然后对于每个询问 [l, r]，设莫队的区间为 [ql, qr]：

  1. 如果 l, r 所在块相同，直接暴力
  2. 如果 l 与上一个询问的 l 所在块不同，那么就把 ql 改成 l 所在块的右端点 + 1，qr 改成 l 所在块的右端点
  3. 向外扩展 qr 直到 r（因为 qr 此时一定小于 r）
  4. 向外扩展 ql 直到 l（因为 ql 此时一定大于 l）
  5. 撤销 ql 的扩展（为了保证复杂度）

块长取 \frac{n}{\sqrt{m}} 的时候复杂度只有 O(n\sqrt{m})

code: 

#include <bits/stdc++.h>
#define eps 1e-12
#define inf LONG_LONG_MAX
#define int long long
#define endl '\n'
using namespace std; 

const int maxn = 1e5 + 10, mod = 1e9 + 7; 
int a[maxn], to[maxn], l[maxn], r[maxn], pos[maxn];
struct node {
    int l, r, id;
    bool operator < (const node &b) { return pos[l] == pos[b.l] ? r < b.r : pos[l] < pos[b.l]; }
} q[maxn];
int b1[maxn], b2[maxn], ans[maxn];
void del(int x) {
    b1[x]--;
}
int add(int x) {
    b1[x]++;
    return b1[x] * to[x];
}
signed main() {
    ios::sync_with_stdio(0); 
    cin.tie(0), cout.tie(0); 
    int n, qq;
    cin >> n >> qq;
    int m = 0, bl = sqrt(n);
    for (int i = 1; i <= n; i++) cin >> a[i], to[++m] = a[i];
    sort(to + 1, to + m + 1);
    m = unique(to + 1, to + m + 1) - to - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(to + 1, to + m + 1, a[i]) - to;
    int tot = 0; // 初始化分块
    for (int i = 1; i <= n; i += bl) {
        l[++tot] = i, r[tot] = min(i + bl - 1, n); 
        for (int j = l[tot]; j <= r[tot]; j++) pos[j] = tot;
    }
    for (int i = 1; i <= qq; i++) cin >> q[i].l >> q[i].r, q[i].id = i; 
    sort(q + 1, q + qq + 1); // 询问排序
    int lst = 0, ql = 1, qr = 0, sum = 0;
    for (int i = 1; i <= qq; i++) {
        if (pos[q[i].l] == pos[q[i].r]) { // 暴力
            int res = 0;
            for (int j = q[i].l; j <= q[i].r; j++) {
                b2[a[j]]++;
                res = max(res, to[a[j]] * b2[a[j]]);
            }
            ans[q[i].id] = res;
            for (int j = q[i].l; j <= q[i].r; j++) b2[a[j]]--;
            continue;
        }
        if (pos[q[i].l] != lst) { // 不同块时移动莫队区间
            while (qr > r[pos[q[i].l]]) del(a[qr--]);
            while (ql < r[pos[q[i].l]] + 1) del(a[ql++]);
            sum = 0, lst = pos[q[i].l];
        }
        while (qr < q[i].r) sum = max(sum, add(a[++qr])); // 移动右指针
        int tmp = sum, ll = ql; // 临时存一下方便撤销
        while (ll > q[i].l) tmp = max(tmp, add(a[--ll])); // 移动左指针
        ans[q[i].id] = tmp; // 记录答案
        while (ll < ql) del(a[ll++]); // 撤销
    }
    for (int i = 1; i <= qq; i++) cout << ans[i] << endl;
    return 0; 
}

二维莫队

实际上就是指针变成 4 个的普通莫队，然后块长取 n\times q^{-\frac{1}{4}}，剩下的基本上都差不多，时间复杂度 O(n^2q^{\frac{3}{4}}+q\log q)

二次离线

树上莫队

配合bitset