专栏文章

莫队

DDJ_Liu
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mind4cvy
此快照首次捕获于
2025/12/02 00:27
3 个月前
此快照最后确认于
2025/12/02 00:27
3 个月前
查看原文
莫队那些的，比如莫队二离、回滚、带修的都会吧，会那不讲了
我：？？？

莫队

莫涛队长（×\times）莫比乌斯队列（√\surd）
莫队可以解决一类离线静态区间询问问题，如果可以 O(1)O(1) 的将 [l,r][l, r] 扩展到 [l,r+1],[l,r−1],[l+1,r],[l−1,r][l, r + 1], [l, r - 1], [l + 1, r], [l - 1, r]，那么便可以用 O(nm)O(n\sqrt{m}) 的复杂度解决
那么作法就显然了，先离线排序，然后暴力的一步一步挪动询问区间来获取答案，而排序就以 ll 所在块为第一关键字，rr 为第二关键字从小到大排序即可，块长取 nm\frac{n}{\sqrt{m}} 即可
复杂度证明参见 OI-wiki（

奇偶化排序

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

例题

[国家集训队] 小 Z 的袜子
区间数颜色，莫队经典题型
code：
CPP
#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,rl, r 的转移顺序不是固定的，目前看来你只要保持 --l 在 l++ 前，++r 在 r-- 前就是对的，玄学

带修

很明显普通莫队无法支持修改，但有些人就是药用莫队维护动态序列，这个时候就要用到带修改莫队解决
具体怎么做呢，只需要再加入一个时间维 tt 就行，排序呢只需要把第二关键字改成 rr 所在块，第三关键字改成 tt 即可
那么怎么维护扩大缩小区间时的修改呢，假设原来 pp 位上的颜色是 aa，如果 pp 在 [l,r][l, r] 内，那么相当于删掉 aa，加上 cc，并且将原数组的第 pp 位修改为 cc，不在的话就直接将原数组的第 pp 位修改为 cc，而如果是去掉这个操作只需要交换 a,ca, c 就行
还有一个问题，这个情况下块长再取 n\sqrt{n} 的话复杂度是劣的，而经过分析 n,m,tn, m, t 同阶时块长取 n2/3n^{2/3} 时是最优的，复杂度是 O(n53)O(n^{\frac{5}{3}})，证明见 OI-wiki（

例题

[国家集训队] 数颜色
模板题，直接做
code：
CPP
#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][l, r]，设莫队的区间为 [ql,qr][ql, qr]：
  1. 如果 l,rl, r 所在块相同，直接暴力
  2. 如果 ll 与上一个询问的 ll 所在块不同，那么就把 qlql 改成 ll 所在块的右端点 + 1，qrqr 改成 ll 所在块的右端点
  3. 向外扩展 qrqr 直到 rr（因为 qrqr 此时一定小于 rr）
  4. 向外扩展 qlql 直到 ll（因为 qlql 此时一定大于 ll）
  5. 撤销 qlql 的扩展（为了保证复杂度）
块长取 nm\frac{n}{\sqrt{m}} 的时候复杂度只有 O(nm)O(n\sqrt{m})
code:
CPP
#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; 
}

二维莫队

二次离线

树上莫队

配合bitset

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...