莫队算法总结

写在前面

莫队算法用于离线解决一类区间问题。


普通莫队

如果我们已知查询为区间[l,r][l,r]的答案,并且能在O(1)O(1)的时间内通过添加或删除一个元素得到[l1,r],[l+1,r],[l,r1],[l,r+1][l-1,r],[l+1,r],[l,r-1],[l,r+1]的答案,那么就可以考虑使用莫队算法。

做法:

  1. 首先我们对原序列分块,原序列长度NN,每块大小记为SizeSize,那么块数为N1Size+1\lfloor \frac{N-1}{Size} \rfloor +1,每块从左到右依次编号。

  2. 对所有询问[li,ri][l_i,r_i]以询问左端点所在块的序号为第一关键字,右端点的大小为第二关键字进行排序。按照这样的顺序通过添加或删除元素求解每个询问的答案。

可以证明当SizeSizeN\sqrt{N}时,总的时间复杂度为O(N1.5)O(N^{1.5})

  • 左端点在同一块时,右端点是递增的,变化NN次,共有N\sqrt{N}个块,这一部分复杂度为O(N1.5)O(N^{1.5})
  • 左端点转移到下一块时,右端点最多变化NN次,共有N\sqrt{N}个块,这一部分复杂度为O(N1.5)O(N^{1.5})
  • 左端点在同一块时,每次最多变化N\sqrt{N},转移到下一块时,最多变化2N2\sqrt{N},询问共NN个,这一部分复杂度为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
const int SIZE=300;
struct Q{int l,r,order;} q[N];
bool cmp(const re &a,const re &b)
{
if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
return a.r<b.r;
}
int main()
{
for(int i=1;i<=n;++i) pos[i]=(i-1)/SIZE+1;
for(int i=1;i<=m;++i) q[i].order=i;
sort(q+1,q+m+1,cmp);
for(int i=1,l=1,r=0; i<=m; ++i)
{
int L=q[i].l ,R=q[i].r;
while(r<R) add(++r);
while(r>R) del(r--);
while(l<L) del(l++);
while(l>L) add(--l)
ans[q[i].order]=now;
}
//for(int i=1; i<=m; ++i) print ans[i]
}

带修改莫队

对于一些带单点修改的问题,还是存在一种莫队姿势的。当然,一次修改要求O(1)O(1)完成。

每个修改操作记录位置和修改前后的值,这样方便还原修改。

每个询问除了记录区间[l,r][l,r]之外,还要记录在此询问之前的修改操作个数(也可以叫做时间)tt,记posxpos_x表示xx所在块的编号。

那么将所有询问按照(posl,posr,t)(pos_l,pos_r,t)做三关键字排序。那么在普通莫队的基础上,再维护一个修改时间就可以了。

可以证明当SizeSizeN23N^{\frac{2}{3}}时,左端点、右端点、以及时间的移动复杂度均为O(N53)O(N^{\frac{5}{3}}),所以总的时间复杂度为O(N53)O(N^{\frac{5}{3}})

懒得分析了。

模板:

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
struct Change
{
int x,y,pre;
}c[N];

struct Ask
{
int l,r,id,time;
}q[N];

bool cmp(const Ask &a,const Ask &b)
{
if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
if(pos[a.r]!=pos[b.r]) return pos[a.r]<pos[b.r];
return a.time<b.time;
}

void change(int i,int l,int r,bool flag)
{
int y=c[i].x;
if(l<=y && y<=r) erase(y);
color[y]=flag?c[i].y:c[i].pre;
if(l<=y && y<=r) insert(y);
}

int main()
{
size=pow(n,2.0/3)+1;
for(int i=1;i<=n;++i) pos[i]=(i-1)/size+1;
sort(q+1,q+numq+1,cmp);
int l=1,r=0,curt=0;
for(int i=1;i<=numq;++i)
{
while(curt<q[i].time) change(++curt,l,r,1);
while(q[i].time<curt) change(curt--,l,r,0);
while(l<q[i].l) erase(l++);
while(q[i].l<l) insert(--l);
while(q[i].r<r) erase(r--);
while(r<q[i].r) insert(++r);
ans[q[i].id]=now;
}
}

回滚莫队

我们经常会遇到这样一种问题,即插入操作十分简单,但是直接删除却非常困难(举个例子,当你要维护最值时)。有没有一种办法避免删除呢?有的,用回滚莫队的姿势就好了~

回滚,rollback,其实意思应该是还原到修改之前。假设当前询问为[l,r][l,r]poslpos_l不变时,右端点一直增加,添加操作好说,和普通莫队一样做,但是左端点怎么办呢?我们可以暂时先不把开头[l,posl×Size][l,pos_l\times Size]这部分添加,然后先存个档,暴力的插入这一小段,得到当前询问的答案后,再读档还原(有些是撤销修改),这就是回滚操作了。

bzoj 4241 历史研究:

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100010
struct ask
{
int l,r,o;
} q[N];
int n,m;
int a[N],hs[N],pos[N],num[N];
ll now;
ll ans[N];
bool cmp(const ask &a,const ask &b)
{
if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
return a.r<b.r;
}
void del(int x)
{
--num[a[x]];
}
void add(int x)
{
++num[a[x]];
now=max(now,1LL*hs[a[x]]*num[a[x]]);
}
int main()
{
scanf("%d%d",&n,&m);
int siz=sqrt(n);
for(int i=1;i<=n;++i)
{
scanf("%d",a+i);
hs[i]=a[i];
pos[i]=(i-1)/siz+1;
}
sort(hs+1,hs+n+1);
int cnt=unique(hs+1,hs+n+1)-hs-1;
for(int i=1;i<=n;++i)
a[i]=lower_bound(hs+1,hs+cnt+1,a[i])-hs;
for(int i=1;i<=m;++i)
{
scanf("%d%d",&q[i].l,&q[i].r);
q[i].o=i;
}
sort(q+1,q+m+1,cmp);
int r=0;
for(int i=1;i<=m;++i)
{
int L=q[i].l,R=q[i].r;
if(pos[q[i].l]!=pos[q[i-1].l])
{
memset(num,0,sizeof(num));
r=pos[q[i].l]*siz;
now=0;
}
while(r<R) add(++r);
ll last=now;
for(int j=L;j<=pos[q[i].l]*siz && j<=R;++j)
add(j);
ans[q[i].o]=now;
//rollback
for(int j=L;j<=pos[q[i].l]*siz && j<=R;++j)
del(j);
now=last;
}
for(int i=1;i<=m;++i)
printf("%lld\n",ans[i]);
return 0;
}

题目

普通莫队

带修改莫队

回滚莫队


莫队算法总结
https://izard.space/2018/05/03/莫队算法总结/
作者
forever_you
发布于
2018年5月3日
许可协议