莫队算法

2020-09-10
5分钟阅读时长
Algorithm , Other

简介

莫队算法是由莫涛发明的，用于处理区间询问的暴力优雅的离线算法，主要基于分块和排序的思想。

问题引入

假设我们要求一个区间[l, r]中含有不同元素的个数，现在已知区间[2, 3]的答案，要求区间[2, 4]的答案，要怎么做呢？我们先开一个cnt[]数组来记录已知答案的区间包含的元素个数，那么求区间[2, 4]时，先将r指针往右移，判断cnt[a[r]]是否为0，为0的话则说明出现了一个新的数字，答案的贡献+1，并且cnt[a[i]]++。所以，对于求任何的区间，我们都可以通过移动左右指针，并且暴力维护区间信息的方式来得到答案。

这个算法非常容易写，这里就不写了~~，(主要是懒)~~

很明显这个算法会存在问题，比如题目要求[1, 2]、[n-1, n]、[1, 2]、[n-1, n]……，那么我们的左右指针就会在两个极端反复横跳，那么必定会TLE。这一个暴力还不够的优雅，所以肯定不是莫队算法，但是离莫队算法很近很近了。

优化

对于上面这种情况，加入我们将询问区间变为[1, 2]、[1, 2]、[1, 2]……[n-1, n]、[n-1, n]、[n-1, n]这样，那么将跑的飞快。所以莫队算法就是将所有询问记录下来，然后根据规则对询问区间进行排序，再通过移动左右指针的方式暴力维护答案。所以莫队算法是处理离线问题的，对于在线问题是束手无措。

在线问题就是必须询问一次回答一次，离线问题就是可以先将全部询问记录下来，最后再一起回答。

那么如何对区间进行排序呢？我们先将区间分为sqrt(n)块，有两个区间a和b，如果a.l和b.l在同一个块里，我们就将根据它们的r排序，否则将l所在块号小的排在前面。

莫队

来看看对于上面的问题，代码究竟怎么写吧

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e6+5;

// 记录询问，k代表第几个询问
struct Q {
	int l, r, k;
}q[maxn];

// pos[i]表示i所在的块号
int pos[maxn], cnt[maxn], ans[maxn], a[maxn];

// 记录区间答案的全局变量
int res;

// 排序规则
bool cmp(Q a, Q b) {
	return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
}

// 加贡献
void add(int x) {
	cnt[a[x]]++;
	res += cnt[a[x]] == 1;
}

// 减贡献
void sub(int x) {
	cnt[a[x]]--;
	res -= cnt[a[x]] == 0;
}

int main() {
	int n;
	scanf("%d", &n);
    // 块大小
	int size = sqrt(n);
	for (int i=1; i<=n; i++) {
		scanf("%d", &a[i]);
        // i所在的块号
		pos[i] = i / size;
	}
	int m;
	scanf("%d", &m);
	for (int i=0; i<m; i++) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].k = i;
	}
	sort(q, q+m, cmp);
    // 注意l和r的初始化不是0 0
	int l=1, r=0;
	for (int i=0; i<m; i++) {
        // 暴力移动区间，注意自增自减运算符的效果
		while (q[i].l < l) add(--l);
		while (q[i].r > r) add(++r);
		while (q[i].l > l) sub(l++);
		while (q[i].r < r) sub(r--);
		ans[q[i].k] = res;
	}
	for (int i=0; i<m; i++) printf("%d\n", ans[i]);
	return 0;
}

莫队算法的整体架构就如上面一样，只是add()和sub()函数的写法需要根据题目要求定制一下，这么一看莫队算法确实是优雅的暴力~

洛谷P2709

来看一道模板题吧

luogu P2709

image-20200909094120601

// 样例输入
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

// 样例输出
6
9
5
2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 2e5+5;


struct Q {
	int l, r, k;
}q[maxn];

int a[maxn], pos[maxn], cnt[maxn];
ll ans[maxn];
ll res;

bool cmp(Q x, Q y) {
	return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l];
}

void add(int x) {
	cnt[a[x]]++;
	res += 1ll * cnt[a[x]] * cnt[a[x]] - 1ll * (cnt[a[x]] - 1) * (cnt[a[x]] - 1);
}

void sub(int x) {
	cnt[a[x]]--;
	res -= 1ll * (cnt[a[x]] + 1) * (cnt[a[x]] + 1) - 1ll * cnt[a[x]] * cnt[a[x]];
}

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	int size = sqrt(n);
	for (int i=1; i<=n; i++) {
		cin >> a[i];
		pos[i] = i / size;
	}
	for (int i=0; i<m; i++) {
		cin >> q[i].l >> q[i].r;
		q[i].k = i;
	}
	sort(q, q+m, cmp);
	int l = 1, r = 0;
	for (int i=0 ;i<m; i++) {
		while (q[i].l < l) add(--l);
		while (q[i].r > r) add(++r);
		while (q[i].l > l) sub(l++);
		while (q[i].r < r) sub(r--);
		ans[q[i].k] = res;
	}
	for (int i=0; i<m; i++) cout << ans[i] << '\n';
	return 0;
}

带修改的莫队

有一些带修改的问题也能用莫队来做，只要不是强制在线就行。

带修莫队和普通莫队没有太大的区别，只是需要维护多一个变量time，普通莫队的移动为[l+1, r]、[l-1, r]、[l, r+1]、[l, r-1]，而带修莫队还需要判断当前时间和查询操作的时间的差异，所以带修莫队的移动为[l+1, r, t]、[l-1, r, t]、[l, r+1, t]、[l, r-1, t]、[l, r, t-1]、[l, r, t+1]。

并且将排序规则改为下面的样子

bool cmp(Q a, Q b) {
	return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.r] ^ pos[b.r]) ? pos[a.r] < pos[b.r] : a.t < b.t);
}

块的大小也由sqrt(n)变为pow(n, 2.0 / 3.0)

干说有点不知道在干嘛，还是看个具体的问题吧。

洛谷P1903

luogu P1903

image-20200909094740495

// 样例输入
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6

// 样例输出
4
4
3
4

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(0)
#define DEBUG(x) cout<<"--->"<<(x)<<endl;
typedef pair<int, int> P;
const ll mod = 1e9+7;
const double eps = 1e-9;
const double PI = acos(-1);
const int maxn = 1e6+5;

// 查询
struct Q {
	int l, r, k, t;
}q[maxn];
// 修改
struct M {
	int p, col;
}c[maxn];
int a[maxn], cnt[maxn], ans[maxn], pos[maxn];
int cntq, cntc, n, m, size;

bool cmp(Q a, Q b) {
	return (pos[a.l] ^ pos[b.l]) ? pos[a.l] < pos[b.l] : ((pos[a.r] ^ pos[b.r]) ? pos[a.r] < pos[b.r] : a.t < b.t);
}

int main() {
	scanf("%d", &n);
	scanf("%d", &m);
    // 块大小与普通莫队不同
	size = pow(n, 2.0 / 3.0);
	for (int i=1; i<=n; i++) {
		pos[i] = i / size;
		scanf("%d", &a[i]);
	}
	for (int i=1; i<=m; i++) {
		char opt[100];
		scanf("%s", opt);
		if (opt[0] == 'Q') {
			++cntq;
			scanf("%d%d", &q[cntq].l, &q[cntq].r);
			q[cntq].k = cntq;
			q[cntq].t = cntc;	// 查询询问的时间戳
		} else {
			++cntc;
			scanf("%d%d", &c[cntc].p, &c[cntc].col);
		}
	}
	sort(q + 1, q + cntq + 1, cmp);
	int l = 1, r = 0, time = 0, res = 0;
    // 为了方便理解，就没有专门写add和sub函数了
	for (int i=1; i<=cntq; i++) {
		int ql = q[i].l, qr = q[i].r, qt = q[i].t;
		while (ql < l) {
			l--;
			cnt[a[l]]++;
			res += cnt[a[l]] == 1;
		}
		while (ql > l) {
			cnt[a[l]]--;
			res -= cnt[a[l]] == 0;
			l++;
		}
		while (qr < r) {
			cnt[a[r]]--;
			res -= cnt[a[r]] == 0;
			r--;
		}
		while (qr > r) {
			r++;
			cnt[a[r]]++;
			res += cnt[a[r]] == 1;
		}
        // 下面两个是针对修改的移动
		while (time < qt) {
			++time;
			if (ql <= c[time].p && c[time].p <= qr) {
				cnt[a[c[time].p]]--;
				cnt[c[time].col]++;
				res -= cnt[a[c[time].p]] == 0;
				res += cnt[c[time].col] == 1;
			}
			swap(a[c[time].p], c[time].col);
		}
		while (time > qt) {
			if (ql <= c[time].p && c[time].p <= qr) {
				cnt[a[c[time].p]]--;
				cnt[c[time].col]++;
				res -= cnt[a[c[time].p]] == 0;
				res += cnt[c[time].col] == 1;
			}
			swap(a[c[time].p], c[time].col);
			--time;
		}
		ans[q[i].k] = res;
	}
	for (int i=1; i<=cntq; i++)
		printf("%d\n", ans[i]);
	return 0;
}

带修莫队只是比普通莫队多维护一维而已，写起来也不难。

推荐视频

AgOH–莫队算法

#Algorithm #Other
上一页 Treap
下一页 替罪羊树

相关

替罪羊树
可持久化并查集
可持久化数组
最大最小表示法
Manacher
扩展KMP