莫队算法总结
内容
一种优秀的暴力,处理区间问题。
区间型问题的暴力写法就是,每次把所有的区间都扫一下,统计一下答案,输出。
但是我们可以发现,有时候查询的区间会是重复的。
比如我们要查询[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 单调队列其实就是一种比较特殊的莫队。
看一道例题
【但是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]); }
可见它的代码量非常和善。
下一道题
题目描述
小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]); }
莫队还有很多,比如树上莫队,带修莫队等。。以后再填坑吧。。