分块算法莫队（代码实现）

站长

2024年04月14日 14:00 · 阅读数 53

莫队概述莫队是一种解决区间查询问题的离线算法。它的思想很简单，本质上就是通过挪动区间的方式按照某种顺序，离线处理区间查询操作。它的时间复杂度是是一种效率不错的算法，可以解决几乎所有的区间查询问题（需要离线），只要对时间复杂度的要求不是那么苛刻。
挪动区间假设有这样的一道题：对于一个数列，每次给出一个区间询问 [L,R] ，求它的区间和。这道题用前缀和很容易做出来，不过我们强制用莫队做。

对于下面的例子，首先要开一个数组存储数列。注意，区间从 1 开始：

0  1  2  3  4  5  6  7  8  9 |index   
   3  8  1  2  7  4  9  0  6 |val

假设我们此时已经知道 [2,5] 区间的和是 18 ，有如下询问：

求 [2,6] 区间的和：用 [2,5] 区间的和，加上第六项的值即可，答案是 18+4=22 ；
求 [2,4] 区间的和：用 [2,5] 区间的和，减去第五项的值即可，答案为 18-7=11 ；
求 [3,6] 区间的和：用 [2,5] 区间的和，减去第二项的值，再加上第六项的值就可以求出；
其他区间依次类推。
由此，对当前区间 [L,R] ，我们分别讨论四种情况：

加上当前区间左边一格 L - 1 处的贡献：Add(--L);
加上当前区间右边一格 R + 1 处的贡献：Add(++R);
减去当前区间最左一格 L 处的贡献：Sub(L++);
减去当前区间最右一格 R 处的贡献：Sub(R--);
可以看到，我们不只是修改了区间的总贡献，还修改了区间的 [L, R] 边界。这样，所有的区间都可以从当前已知区间的结果扩展出来。

某种顺序和离线处理仅仅这样是远远不够的，对于一个 n 项的数列，假设这样询问 m 次：

分块算法莫队（代码实现）

那么怎样排序来解决询问顺序呢？很容易想到使用l 作为第一个关键字、r 作为第二关键字进行排序，但这样的效果不是很好。为此，我们需要使用分块进行优化。具体做法如下：

分块算法莫队（代码实现）

然后对所有的询问进行排序，排序规则如下：对于一个询问 [L,R] ，
首先按照区间的 L 边界所在块的编号从小到大排序；对于处在同一块的，按照 R 的大小进行排序；
排序后，遍历所有询问，进行区间的移动，得到各个询问的答案记录下来；
最后，按照这些询问的原顺序输出答案即可。
看完上面的过程，我们就能够明白，为什么莫队要求离线。

莫队算法框架下面给出基础莫队的代码框架：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 5;

int a[maxn];	 //记录所有数据的数组
int pos[maxn];   //a数列中的第几项是第几块的 
int ans[maxn];   //记录所有询问的答案(按照原来的顺序)
//询问的结构体
struct Q {
	int l, r, k; //询问的区间[l,r], 第几个询问 
} q[maxn];
//记录某一个由[L,R]规定的闭区间的区间结果
int res = 0;
//挪动区间的函数
void Add(int n) { ... }
void Sub(int n) { ... }

int main() {
	//n个数据,m个询问
	int n, m;
	cin >> n >> m;
	//记录数据和分块
	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;		   //第几个询问,用来记录询问的原始顺序
	}
	//所有询问进行排序,同一个块按照r排序,否则按照块顺序排
	sort(q, q + m, [](Q x, Q y) 
		{ return pos[x.l] == pos[y.l] ? x.r < y.r : pos[x.l] < pos[y.l] }); 
	//当前所知的闭区间[l,r]
	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;
	}
	//输出ans数组作为答案
	...
    return 0;
}

常数优化：奇偶化排序上面的分块排序，就可以有效降低每两次询问间 l , r l, rl,r 移动的距离。但在此之上，我们还可以进行常数优化：奇偶化排序。即块号 pos[l] 不相等时，按照块号从小到大排序；相等时如果 pos[l] 是奇数，则将 r 从小到大排序，否则按照 r 从大到小排序。为什么它是有效的？

如果按照一般的排序方法，指针会这样移动：在 l 处于同一块时，指针 r 不断往右移；每当 l 跨越一个块时，r 都必须从右向左移动很长一段距离：

分块算法莫队（代码实现）

而奇偶化排序后，指针会这样移动：在 l 处于奇数块时，指针 r 不断往右移，解决所有块内的询问；l 跨越到下一块（偶数块）时，r 指针不断往左移，在返回的过程中解决按照 r 从大到小排序的询问：

分块算法莫队（代码实现）

询问的结构体代码如下：

const int MAXN = 1e5 + 10;
int sqr = sqrt(n);
struct Q {
	int l, r, id;
	bool operator<(const Q &b) const { //重载<运算符,奇偶化排序
		//只需要知道每个元素归属于哪个块,块大小为sqrt(n),所以直接l/sqrt(n)即可
		if (l / sqr != b.l / sqr) return l < b.l;
		if (l / sqr & 1) //奇数块
			return r < b.r;
		return r > b.r;
	}
} Q[MAXN];

洛谷 P2709 小B的询问【莫队】
代码如下：
#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e4 + 10;
int a[maxn];				//记录数据,值域为[1,k] 
int pos[maxn];
long long ans[maxn];		//结果可能超过int范围 
long long res = 0;			//记录闭区间结果 
int cnt[maxn]; 				//[1,k]值域的数ci出现几次 
struct Q {
	int l, r, i;			//[l,r]闭区间,i表示第几个询问 
} q[maxn];
//区间[l,r]的总贡献是其中每个数的出现次数的平方和 
//区间扩展时,扩展的某格的数a[n]的出现次数+1,
//我们需要减去该格的数原来出现次数的平方,加上该格数新的出现次数的平方 
//一个小优化:(a+1)^2-a^2=2a+1 
void Add(int n) {
	res += (2 * cnt[a[n]] + 1);
	++cnt[a[n]]; 
}
//区间收缩时,收缩的某格的数a[n]的出现次数-1,
//我们需要减去该格的数原来出现次数的平方,加上该格数新的出现次数的平方
//一个小优化:(a-1)^2-a^2=-2a+1 
void Sub(int n) {
	res += (1 - 2 * cnt[a[n]]);
	--cnt[a[n]];
}

int main() {
    int n, m, k;
    scanf("%d%d%d", &n, &m, &k);
    int size = sqrt(n);
    for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[i] = i / size;
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].i = i;
	}
	sort(q, q + m, [](const Q &a, const Q &b) {
		return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
	});
	//闭区间[l,r] 
	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].i] = res;
    }
    //打印结果
	for (int i = 0; i < m; ++i) 
		printf("%lld\n", ans[i]); 
    return 0;
}

洛谷 P3901 数列找不同【莫队】
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int a[maxn];
int pos[maxn];
bool ans[maxn];		//第几个询问的区间中是否每个数都互不相同 
int cnt[maxn];		//记录区间[l,r]中的每个数的出现次数 
struct Q {
	int l, r, i;
} q[maxn];
//题目询问的是区间[l,r]中的所有数是否互不相同,转换为
//[l,r]中互不相同的数的个数是否等于区间大小r-l+1,等于则互不相同,否则存在相同的数 
int res = 0;		//[l,r]中互不相同的数的个数

void Add(int n) { ++cnt[a[n]]; if (cnt[a[n]] == 1) ++res; } //出现了一个不同的数,res++ 
void Sub(int n) { --cnt[a[n]]; if (cnt[a[n]] == 0) --res; } //失去了一个不同的数,res-- 

int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int size = sqrt(n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
		pos[i] = i / size;
	}
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &q[i].l, &q[i].r);
		q[i].i = i;
	}
	sort(q, q + m, [](const Q &a, const Q &b) {
		return pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l];
	});
	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--);
		//第几个询问的答案是区间[l,r]中互不相同的数的个数 
		//等于区间大小r-l+1则互不相同,否则存在相同的数  
		ans[q[i].i] = (res == r - l + 1) ? true : false; 
	}
	for (int i = 0; i < m; ++i) 
		printf("%s\n", ans[i] ? "Yes" : "No"); 
    return 0;
} 

SPOJ DQUERY - D-query【莫队】

思路：普通莫队+奇偶化排序。代码如下：

//题目链接：https://www.spoj.com/problems/DQUERY/
//其实可以取消pos数组记录块号的 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e4 + 10, maxq = 2e5 + 10, maxm = 1000005;
int a[maxn], cnt[maxm], n, q, sqr;
struct Q {
	int l, r, id;
	bool operator<(const Q &b) const {
		if (l / sqr != b.l / sqr) //先按照左边界的块号从小到大排序 
			return l < b.l;
		else if (l / sqr & 1) //块号相等时,如果是奇数块,按照右边界r从小到大排序 
			return r < b.r;
		return r > b.r;	//偶数块 
	}
} query[maxq];
int ans[maxq];
int res = 0;
void Add(int n) {
	if (cnt[a[n]] == 0) ++res;
	++cnt[a[n]];	
}
void Sub(int n) {
	--cnt[a[n]];
	if (cnt[a[n]] == 0) --res;
}

int main() { 
	scanf("%d", &n);
	sqr = sqrt(n);
	for (int i = 1; i <= n; ++i) 
		scanf("%d", &a[i]); 
	scanf("%d", &q);
	for (int i = 0; i < q; ++i) {
		scanf("%d%d", &query[i].l, &query[i].r);
		query[i].id = i;
	}
	sort(query, query + q);
	int l = 1, r = 0;
	for (int i = 0; i < q; ++i) {
		while (l > query[i].l) Add(--l);
		while (r < query[i].r) Add(++r);
		while (l < query[i].l) Sub(l++);
		while (r > query[i].r) Sub(r--);
		ans[query[i].id] = res;
	}
    for (int i = 0; i < q; ++i)
        printf("%d\n", ans[i]); // 按编号顺序输出
    return 0;
}

博客来源：(https://blog.csdn.net/myrealization/category_10329158.html)

转载自:https://juejin.cn/post/7043415647786631182

分块算法 莫队（代码实现）

分块算法莫队（代码实现）