首页 > 笔记 > 莫队算法总结

莫队算法总结

一种优秀的暴力,处理区间问题。

区间型问题的暴力写法就是,每次把所有的区间都扫一下,统计一下答案,输出。

但是我们可以发现,有时候查询的区间会是重复的。

比如我们要查询[1,5][2,7],这样的话[2,5]的区间就被查询了两次,非常的令人不爽。

我们就可以想象有一个正在查询的[l,r]区间,每次我们移动一下l\r指针,来达到查询的目的。

比如,我们现在查到了[1,5],下一个查询区间是[2,7]

我们就可以把l指针向右移动1,把1这个地方值所作出的贡献减去,把r指针向右移2,把6、7作出的贡献加上,就得到了答案。

是不是非常简单。

但是我们就面临的一个问题,如何排列询问的区间让所用的移动数最小。

可以简单的想一下,能不能直接左端点排序。

举个例子,有6个询问如下:(1, 100), (2, 2), (3, 99), (4, 4), (5, 102), (6, 7)。

这个数据已经按照左端点排序了。用上述方法处理时,左端点会移动6次,右端点会移动移动98+97+95+98+95=483次。右端点大幅度地来回移动,严重影响了时间复杂度——排序的复杂度是O(mlogm),所有左端点移动次数仅为为O(n),但右端点每个询问移动O(n),共有m个询问,故总移动次数为O(nm),移动总数为O(mlogm + nm)。运行时间上界并没有减少。

其实我们稍微改变一下询问处理的顺序就能做得更好:(2, 2), (4, 4), (6, 7), (5, 102), (3, 99), (1, 100)。

左端点移动次数为2+2+1+2+2=9次,比原来稍多。右端点移动次数为2+3+95+3+1=104,右端点的移动次数大大降低了。

所以不能直接排序,我们需要稍稍变通一下,让左右端点“大概”处于升序状态。

具体实现的话,我们可以把数据分成几块,让块的左端点升序,块内的右端点升序,这样就非常的和善了。

这样对于左端点当然不是最优的,对于右端点也当然不是。但是,我们可以取得一个“适当”的效率,尽量满足两方需求。

这也是莫队分块的核心思想。多少分一个块最优呢?

平时,我们就可以直接分\( \sqrt n\)个块。证明一下效率:

0:我们先假设通过[l,r]求得[l,r+1],[l,r-1],[l-1,r],[l+1,r]的效率是\( O(1) \)或\( O( \log n) \)的(反正需要比较快的转变);

1:对于左端点在同一块中的询问:
右端点转移的时间复杂度是\( O( \sqrt n) \),一共有\( \sqrt n \)块,所以右端点转移的时间复杂度是\( O(n \sqrt n) \)
左端点每次转移最差情况是\( O( \sqrt n) \),左端点在块内会转移n次,左端点转移的时间复杂度是\( O(n \sqrt n) \);

2:对于左端点跨越块的情况:
会跨区间\( O( \sqrt n) \)次;
左端点的时间复杂度是\( O( \sqrt n \times \sqrt n ) \)=\( O(n) \)可以忽略不计
右端点因为在跨越块时是无序的,右端点跨越块转移一次最差可能是\( O(n) \),可能跨越块转移\( \sqrt n \)次,所以时间复杂度是\( O(n \sqrt n) \)

所以总的来说莫队的时间复杂度是\( O(n \sqrt n) \);

我们需要真正考虑的,就是我们的第一条:通过[l,r]求得[l,r+1],[l,r-1],[l-1,r],[l+1,r]的效率是较快的。也就是是当你的区间增加某个节点,答案改变了多少?减少了某个节点,答案又会改变多少?

搞明白这个,问题也就解决了。


update 2017-3-18 单调队列其实就是一种比较特殊的莫队。

看一道例题

luogu1972

【但是luogu数据过水,建议在cv2307

题目描述

HH 有一串由各种漂亮的贝壳组成的项链。HH 相信不同的贝壳会带来好运,所以每次散步完后,他都会随意取出一段贝壳,思考它们所表达的含义。HH 不断地收集新的贝壳,因此,他的项链变得越来越长。有一天,他突然提出了一个问题:某一段贝壳中,包含了多少种不同的贝壳?这个问题很难回答……因为项链实在是太长了。于是,他只好求助睿智的你,来解决这个问题。

输入输出格式

输入格式:

第一行:一个整数N,表示项链的长度。

第二行:N 个整数,表示依次表示项链中贝壳的编号(编号为0 到1000000 之间的整数)。

第三行:一个整数M,表示HH 询问的个数。

接下来M 行:每行两个整数,L 和R(1 ≤ L ≤ R ≤ N),表示询问的区间。

输出格式:

M 行,每行一个整数,依次表示询问对应的答案。

输入输出样例

输入样例#1:

6
1 2 3 4 3 5
3
1 2
3 5
2 6

输出样例#1:

2
2
4

说明

数据范围:

对于100%的数据,N <= 50000,M <= 200000。

我们要先保证通过[l,r]求得[l,r+1],[l,r-1],[l-1,r],[l+1,r]的效率是\( O(1) \)的

其实这是很容易看出来的,我们可以开一个桶,假如添加一个数的话,它在桶里没有出现过,总答案+1,减少一个数,它减少后桶中就没有东西了,那么总答案-1;

然后乱搞就行了

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define T 1000010
#define N 1000000
#define M 1000000
using namespace std;
struct quest
{
	int l,r,id,num;
}q[M];
bool comp(quest a,quest b)
{
	return a.id==b.id?a.r<b.r:a.id<b.id;
}
int l,r,anslist[N],ton[T],a[N],n,m,k;
main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i;
	int chunk=sqrt(n);
	for (int i=1;i<=m;i++)
		q[i].id=q[i].l/chunk+1;
	sort(q+1,q+m+1,comp);
	l=q[1].l,r=q[1].l;
	int ans=1;
	ton[a[l]]++;
	for (int i=1;i<=m;i++)
	{
		while(l<q[i].l)
		{
			ton[a[l]]--;
			if (!ton[a[l]])
				ans--;
			l++;
		}
		while(l>q[i].l)
		{
			l--;
			if (!ton[a[l]])
				ans++;
			ton[a[l]]++;
		}
		while(r>q[i].r)
		{
			ton[a[r]]--;
			if (!ton[a[r]])
				ans-=1;
			r--;
		}
		while(r<q[i].r)
		{
			r++;
			if (!ton[a[r]])
				ans+=1;
			ton[a[r]]++;
		}
		anslist[q[i].num]=ans;
	}
	for (int i=1;i<=m;i++)
		printf("%d\n",anslist[i]);
}

可见它的代码量非常和善。

下一道题

luogu2709

题目描述

小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求Sigma(c(i)^2)的值,其中i的值从1到K,其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。

输入输出格式

输入格式:

第一行,三个整数N、M、K。

第二行,N个整数,表示小B的序列。

接下来的M行,每行两个整数L、R。

输出格式:

M行,每行一个整数,其中第i行的整数表示第i个询问的答案。

输入输出样例

输入样例#1:

6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6

输出样例#1:

6
9
5
2

说明

对于全部的数据,1<=N、M、K<=50000

我们可以看到,对于增加一个数,可以直接加上\(2 \times 桶中数量 +1\),减去的话就减\(2 \times 桶中数量 +1\)。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 50010
using namespace std;
struct quest
{
	int l,r,id,num;
}q[N];
bool comp(quest a,quest b)
{
	return a.id==b.id?a.r<b.r:a.id<b.id;
}
int l,r,anslist[N],ton[N],a[N],n,m,k;
int get(int x)
{
	return 2*ton[a[x]]+1;
}
main()
{
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++)
		scanf("%d%d",&q[i].l,&q[i].r),q[i].num=i;
	int chunk=sqrt(n);
	for (int i=1;i<=m;i++)
		q[i].id=q[i].l/chunk+1;
	sort(q+1,q+m+1,comp);
	l=q[1].l,r=q[1].l;
	int ans=1;
	ton[a[l]]++;
	for (int i=1;i<=m;i++)
	{
		while(l<q[i].l)
		{
			ton[a[l]]--;
			ans-=get(l);
			l++;
		}
		while(l>q[i].l)
		{
			l--;
			ans+=get(l);
			ton[a[l]]++;
		}
		while(r>q[i].r)
		{
			ton[a[r]]--;
			ans-=get(r);
			r--;
		}
		while(r<q[i].r)
		{
			r++;
			ans+=get(r);
			ton[a[r]]++;
		}
		anslist[q[i].num]=ans;
	}
	for (int i=1;i<=m;i++)
		printf("%d\n",anslist[i]);
}

莫队还有很多,比如树上莫队,带修莫队等。。以后再填坑吧。。