区间神器——莫队

问题概述

在处理区间问题时,如果一类题目满足已知区间[L,R][L,R]的答案后,我们可以O(1)O(1)处理出[L+1,R],[L1,R],[L,R+1],[L,R1][L+1,R],[L-1,R],[L,R+1],[L,R-1]的答案,且可以离线处理的话,我们就可以用莫队算法在均摊时间复杂度为O(N1.5)O(N ^{1.5})的复杂度内解决此类区间问题。 为什么说它是区间神器呢?那是因为它的常数非常小,大多数区间题目都能用莫队算法水过

算法思想/流程

注:因为大多数题目的总区间长度与查询次数的范围相同,以下均将总区间长度与查询次数视为N 以HH的项链(洛谷P1972)为例 我们先设p[i]表示i是否在当前所要查找的区间内 cnt[i]表示i出现的次数 cl表示左指针,cr表示右指针 那么有暴力算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+100;
int n,m;
int N;
int a[maxn],p[maxn];
struct node{
int l,r,id;
}q[maxn];
int ans[maxn],cnt[maxn];
int sum=0;
inline void update(int x){
if(p[x]){
cnt[a[x]]--;
if(!cnt[a[x]])sum--;
}
else {
cnt[a[x]]++;
if(cnt[a[x]]==1)sum++;
}
p[x]=!p[x];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&n);
N=sqrt(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].id=i;
}
int cl=1,cr=0;
for(int i=1;i<=m;i++){
while(cr<q[i].r)update(++cr);
while(cr>q[i].r)update(cr--);
while(cl<q[i].l)update(cl++);
while(cl>q[i].l)update(--cl);
ans[q[i].id]=sum;
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

这个算法理解其实很很简单,手玩几组数据就能搞懂了,但是要注意update()时++cr cr++ ++cl cl++的区别, 也就是添加或者删除操作时包不包括当前区间的左/右指针。这个多推几组数据也能很容易理解。 但是,我们这样做时间复杂度显然非常大,我们发现,在查询操作时,左指针和右指针来来回回跑了很多次,做了很多次无用功。 那么我们可以考虑将其分块处理,将查询的区间以左端点所在块为第一关键字,右端点为第二关键字进行排序,然后再使用上述暴力算法。 因为右端点最多移动n*S(S为块大小)次,而左端点最多移动N2S\frac{N^2}{S} 次, 所以总的时间复杂度为O(N2S+NS)O(\frac{N^2}{S}+{NS})用均值不等式易证出, 当S取(N)\sqrt(N)时,时间复杂度最小,为O(N1.5)O(N^{1.5})

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200000+100;
int n,m;
int N;
int a[maxn],p[maxn];
struct node{
int l,r,id;
}q[maxn];
inline int cmp(node x,node y){
if((x.l/N)==(y.l/N))return x.r<y.r;
return (x.l)<(y.l);
}
int ans[maxn],cnt[maxn];
int sum=0;
inline void update(int x){
if(p[x]){
cnt[a[x]]--;
if(!cnt[a[x]])sum--;
}
else {
cnt[a[x]]++;
if(cnt[a[x]]==1)sum++;
}
p[x]=!p[x];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&n);
N=sqrt(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].id=i;
}
sort(q+1,q+m+1,cmp);
int cl=1,cr=0;
for(int i=1;i<=m;i++){
while(cr<q[i].r)update(++cr);
while(cr>q[i].r)update(cr--);
while(cl<q[i].l)update(cl++);
while(cl>q[i].l)update(--cl);
ans[q[i].id]=sum;
}
for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
return 0;
}

这就是不带修改的莫队算法 其实莫队也是可以带修改的 但是带修改的莫队我理解的还不是很透彻,这个坑先留着,到时候再填

感谢你的赞赏!