Steven_MengのBlog

其实这是一篇咕了很久的学习笔记。

本人比较喜欢莫队这种根号算法。

以上是博主瞎扯淡,下面正文开始。

莫队基本原理

何为莫队,莫队可不是一个队列,他是以集训队大佬莫涛为名的暴力算法(又称对询问分块)。

其实思路比较简单,我们现在得到了查询$[l_1,r_1]$的答案,想要通过比较少的代价获得$[l_2,r_2]$的答案,怎么办。

一个很简单的思路,就是先把$l_1$移动到$l_2$的位置,同时从当前状态减去$[l_1,l_2-1]$对应的元素,再把$r_1$移动到$r_2$的位置,从当前状态加上$[r_1+1,r_2]$对应的元素。

可能你会比较懵逼,什么叫做加上,减去?

以区间询问不同的数的个数为例,加上这个数的同时更新$cnt[]$数组,还要更新答案,如下:

1
2
3
4
inline void Add(int x){
++cnt[x];
if (cnt[x]==1) ans++;//这个数是最新出现的
}

减去也是同理

1
2
3
4
inline void Del(int x){
--cnt[x];
if (cnt[x]==0) ans--;//这个数被减没了
}

核心代码:

1
2
3
4
while (l<Q[i].l) Del(seq[l++]);
while (l>Q[i].l) Add(seq[--l]);
while (r<Q[i].r) Add(seq[++r]);
while (r>Q[i].r) Del(seq[r--]);

好了,貌似这样更新答案,能少很多运算过程。

$No!$,考虑这样的询问:

$l_1=1,r_1=1$

$l_2=n,r_2=n$

$l_3=1,r_3=1$

……

显然每次询问是$O(n)$的,加上询问变成$O(nm)$的,gg。

这时,莫涛大佬不禁说:“对询问离线,然后排序!”

经过大佬的指点,很多人都可以口胡出一个貌似时间复杂度正确的解法:

对询问离线,然后按照左端点为第一关键字,右端点为第二关键字排序!

代码如下:

1
2
3
4
inline bool operator < (const Query &A,const Query &B){
if (A.l==B.l) return A.r<B.r;
else return A.l<B.l;
}

然鹅,这个是错误的。

考虑这样的询问:

$l_1=1,r_1=1$

$l_2=2,r_2=n$

$l_3=3,r_3=1$

$l_4=4,r_4=n$

……

每次询问还是$O(n)$。

这下怎么搞?

莫涛大佬有一个非常毒瘤的$idea$。

考虑分块,大小为$\sqrt n$,

对询问离线,然后按照左端点所在块编号为第一关键字排序,右端点为第二关键字排序。

代码如下:

1
2
3
4
inline bool operator < (const Query &A,const Query &B){
if (id[A.l]==id[B.l]) return A.r<B.r;
else return id[A.l]<id[B.l];
}

这样为什么是对的呢?

假设我们整体来看,会发现只要左端点每次移动的距离不会超过$2 \times \sqrt n$(可能是在同一个块里面移动,也有可能是从一个块跳到相邻的块),然后右端点整个询问全部加起来也不会移动超过$n\sqrt n$次(因为左端点在同一个块的时候,右端点移动的距离不会超过$n$,而且只有$\sqrt n$个块),均摊$\sqrt n$。

于是发现询问的平均时间复杂度为$O(\sqrt n)$。

妙不妙?

优化方法

同时,我还要介绍莫队的优化方法(奇偶性排序)。

考虑我们左端点从一个块跳到右边相邻的块的过程,在左端点在前一个块的时候,我们的右端点已经到达了一个编号较大的位置,但是左端点一跳到相邻的块,右端点就要跳到一个编号较小的位置,这样虽然不影响时间复杂度,但是总觉得有些浪费,于是我们想,相邻的块和前一个块右端点按照不同的方式排序(比如前一个块从小到大,后一个块从大到小),常数就可以减少。

代码如下:

1
2
3
4
5
6
7
inline bool operator < (const Query &A,const Query &B){
if (id[A.l]==id[B.l]){
if (id[A.l]&1) return A.r<B.r;
else return A.r>B.r;
}
else return id[A.l]<id[B.l];
}

按照这种方法排序,听说常数能够减少很多。


下面进入快乐的刷题时间:

普通莫队

先从简单的普通莫队练起。

(HH的项链卡莫队,所以没有放进例题)

例题1

P3901 数列找不同

只要区间出现次数超过$2$的数就可以搞定了(代码中是$cnt2$)。

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
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Query{
int l,r,id;
}q[MAXN];
int pos[MAXN];
inline bool operator < (const Query &a,const Query &b){
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&((pos[a.l]&1)?a.r<b.r:a.r>b.r));//奇偶性排序的压行写法
}
int a[MAXN],cnt[MAXN],cnt2;
inline void Add(int x){
++cnt[x];
if (cnt[x]==2) cnt2++;
}
inline void Del(int x){
--cnt[x];
if (cnt[x]==1) cnt2--;
}
int Ans[MAXN];
int main(){
int n=read(),m=read();
int Size=sqrt(n);
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
q[i]=Query{read(),read(),i};
}
sort(q+1,q+1+m);
int l=1,r=0;
for (register int i=1;i<=m;++i){
while (l<Q[i].l) Del(seq[l++]);
while (l>Q[i].l) Add(seq[--l]);
while (r<Q[i].r) Add(seq[++r]);
while (r>Q[i].r) Del(seq[r--]);
Ans[q[i].id]=(cnt2==0);
}
for (register int i=1;i<=m;++i){
puts(Ans[i]?"Yes":"No");
}
}

例题2

P1494 [国家集训队]小Z的袜子

设$[L,R]$所有袜子构成的集合是$S$,设$f(x)=x \times (x-1)/2$,显然$ans=\sum _{x \in S} (f(cnt(x))) / f(L-R+1) $。

注意到可以消掉那个$2$,并且拆开$x \times (x-1)$,变成$(\sum_{x \in S}(cnt(x)^2)-\sum_{x \in S} cnt(x)) / (R-L+1) \times (R-L)$

注意到$\sum _{x \in S} cnt(x) = R-L+1$。

于是我们要求的就是$\sum_{x \in S}(cnt(x)^2)$。

可以大力算出来。

(好久以前的代码,码风请原谅)

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
71
72
73
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define MAXN 50005
#define int long long
using namespace std;
int num[MAXN];
struct fen{
int a,b;
inline void yue(){
int g=__gcd(a,b);
a/=g,b/=g;
}
}ans[MAXN];
int pos[MAXN];
struct query{
int l,r,id;
inline int len(){
return r-l+1;
}
}querys[MAXN];
bool operator < (const query &a,const query &b){
if (pos[a.l]==pos[b.l]){
return a.r<b.r;
}
else{
return a.l<b.l;
}
}
int cnt[MAXN];
inline void Change(int &curans,const int &id,const int &val){
curans-=cnt[num[id]]*cnt[num[id]];
cnt[num[id]]+=val;
curans+=cnt[num[id]]*cnt[num[id]];
}
#undef int
int main(){
#define int long long
int n,m;
scanf("%lld%lld",&n,&m);
int sz=sqrt(n);
for (int i=1;i<=n;++i){
pos[i]=(i-1)/sz+1;
}
for (int i=1;i<=n;++i){
scanf("%lld",&num[i]);
}
for (int i=1;i<=m;++i){
scanf("%d%d",&querys[i].l,&querys[i].r);
querys[i].id=i;
}
sort(querys+1,querys+1+m);
int l=1,r=0;
int curans=0;
for (int i=1;i<=m;++i){
while (r<querys[i].r) Change(curans,++r,1);
while (r>querys[i].r) Change(curans,r--,-1);
while (l>querys[i].l) Change(curans,--l,1);
while (l<querys[i].l) Change(curans,++l,-1);
if (querys[i].l==querys[i].r){
ans[querys[i].id].a=0,ans[querys[i].id].b=1;
}
else {
ans[querys[i].id].a=curans-(querys[i].len());
ans[querys[i].id].b=querys[i].len()*(querys[i].len()-1);
ans[querys[i].id].yue();
}
}
for (int i=1;i<=m;++i){
printf("%lld/%lld\n",ans[i].a,ans[i].b);
}
}

有技巧的莫队

莫队算法套路千变万化,有必要掌握几个常用的技巧。

例题3

P3674 小清新人渣的本愿

莫队还能和$\rm bitset$结合?

这道题需要运用一些小技巧。

设现在莫队指针$l,r$维护的区间中不同的数组成的集合为${a_1,a_2,a_3…a_n}$

我们维护这样一个$\rm bitset$$s$,对于$a_i$,$s[a_i]=1$

Query1

考虑如何实现查询$x-y=n$,发现$x=y+n$,所以对于所有出现在$a$集合中的数$a_i$,查询$a_i+n$在$a$集合中有没有出现即可。

这个可以通过操作$(s \text{&} (s<<n)).any()$实现,其中$any()$查询$\rm bitset$中有没有$1$

Query2

考虑实现查询$x+y=n$,其实本质和上面一种一样,就是化成$x=-y+n$,再维护一个下标为$-a_i$的$\rm bitset$$s1$即可,但是这样做会有一个严重的问题,$\rm bitset$下标不能为负数。

考虑给$-a_i$加上一个很大的正数$N$,这里使用$MAXN-1$

把$s1$维护的数变为集合$b_i=-a_i+N$,原来的式子化成$x=-y+N+n-N$

查询的操作转换成查询$b_i+n-N$有没有在$a_i$中出现。

注意到$n-N$为负数,于是左移$n-N$转换成右移$N-n$。

通过操作$(s \text{&} (s1>>(N-n))).any()$实现。

Query3

这个比较简单,将$xy=n$转换成$x=\frac{n\dfrac,于是$O(\sqrt{n})$枚举$n$的所有因数即可。

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
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
bitset<MAXN>s,s1;
int a[MAXN],cnt[MAXN],pos[MAXN];
inline void Add(int x){
if (cnt[x]++==0) s[x]=1,s1[MAXN-1-x]=1;
}
inline void Del(int x){
if (--cnt[x]==0) s[x]=0,s1[MAXN-1-x]=0;
}
struct Query{
int opt,l,r,x,id;
}q[MAXN];
inline bool operator < (const Query &a,const Query &b){
return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:((pos[a.l]&1)?a.r<b.r:a.r>b.r);
}
int ans[MAXN];
int main(){
int n=read(),m=read();
int Size=(int)(sqrt(n));
for (register int i=1;i<=n;++i){
a[i]=read();
pos[i]=(i-1)/Size+1;
}
for (register int i=1;i<=m;++i){
int opt=read(),l=read(),r=read(),x=read();
q[i]=Query{opt,l,r,x,i};
}
sort(q+1,q+1+m);
int l=1,r=0;
for (register int i=1;i<=m;++i){
while (l<q[i].l) Del(a[l++]);
while (l>q[i].l) Add(a[--l]);
while (r>q[i].r) Del(a[r--]);
while (r<q[i].r) Add(a[++r]);
if (q[i].opt==1){
ans[q[i].id]=(s&(s<<(q[i].x))).any();
}
else if (q[i].opt==2){
ans[q[i].id]=(s&(s1>>(MAXN-1-q[i].x))).any();
}
else if (q[i].opt==3){
for (register int j=1;j*j<=q[i].x;++j){
if (q[i].x%j!=0) continue;
if (s[j]&&s[q[i].x/j]){
ans[q[i].id]=1;
break;
}
}
}
}
for (register int i=1;i<=m;++i){
puts(ans[i]==1?"hana":"bi");
}
}

例题4

U80812 相同颜色对

莫队可以套上容斥,达到$4$个指针$\to $$2$个指针的效果。

题解

例题5

P5071 [Ynoi2015]此时此刻的光辉

小范围前缀和,大范围莫队是哪个毒瘤想出来的?

题解

例题6

P4689 [Ynoi2016]这是我自己的发明

子树拍平,变成“上树莫队”。

题解


带修莫队

只要再维护一个修改的指针就可以辣!

例题7

P1903 [国家集训队]数颜色 / 维护队列

我们来想一想莫队如何支持修改,我们把查询和修改操作离线下来,如图,将查询标为蓝色,将修改标为红色。

假设我们要查询六号查询的答案,考虑哪些修改会影响答案,肯定是在六号之前的修改,且这些修改的下标$ind$在六号查询的区间$[l,r]$之内,如图中$2$,$4$号修改,要把这些修改全部做完,才能得到正确的结果。

所以,我们在每个查询中除了$l,r,id$,还要记录一个$last$,代表最近的修改位置,查询时,我们要把$last$前面的修改全部做完,如代码。

1
2
3
struct Query{
int l,r,id,last;//last为最近的修改位置
}q[MAXN];

同时记录每个修改操作,只用记录修改的下标$ind$和修改的值$val$即可。

1
2
3
struct Update{
int ind,val;//把ind修改成val
}u[MAXN];

为了做带修莫队,我们记录一个指针$p$ ,代表我们把$[1,p]$的修改操作全部做完了,做莫队的时候,除了常规的莫队操作,还要有下面两行:

1
2
while (p<q[i].last) Upd(++p,i);
while (p>q[i].last) Upd(p--,i);

如果操作做少了,那么我们调用$Upd(++p,i)$,多做一次操作,如果操作做少了,我们调用$Upd(p—,i)$,撤销一次操作。

那么这个撤销怎么弄呢?

很容易想到的是,我们在每个$Update$结构体里面再多存一个$flag$,代表当前是增加操作还是撤销操作,如果是撤销操作,那么我们删除$u[p].val$,加入$num[u[p].ind]$,每次操作后,$flag$取反,即撤销操作变成加入操作,加入操作变成撤销操作。

但是呢,这样代码量不但增加,常数也增多了,这道题你可能$TLE$,考虑有没有更加简洁优美的方法替代$flag$。

有!

我们每次操作之后,将$num[u[p].ind]$和$u[p].val$对调,我们再撤销回去的时候,就相当于将$u[p].val$改成$num[u[p].ind]$,非常巧妙。

实现如下,注意只有修改的下标在现在查询范围之内才会对答案造成影响:

1
2
3
4
5
6
inline void Upd(int p,int i){
if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
Del(num[u[p].ind]),Add(u[p].val);//修改,先删去原有的,再加进val
}
swap(num[u[p].ind],u[p].val);
}

注意要加$sort$,(虽然我不加$sort$也卡过)

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
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
struct Query{
int l,r,id,last;//last为最近的修改位置
}q[MAXN];
struct Update{
int ind,val;//把ind修改成val
}u[MAXN];
int pos[MAXN],num[MAXN];
inline bool operator < (const Query &x,const Query &y){
if(pos[x.l]!=pos[y.l]) return pos[x.l]<pos[y.l];
if(pos[x.r]!=pos[y.r]) return pos[x.r]<pos[y.r];
return x.last<y.last;
}
int cntq,cntu;
inline char gc(){
char ch=getchar();
while (ch!='Q'&&ch!='R') ch=getchar();
return ch;
}
int ans,Ans[MAXN];
static int cnt[MAXN];
#define Add(x) (++cnt[x]==1)?++ans:0
#define Del(x) (--cnt[x]==0)?--ans:0
inline void Upd(int p,int i){
if (q[i].l<=u[p].ind&&u[p].ind<=q[i].r){
Del(num[u[p].ind]),Add(u[p].val);//修改,先删去原有的,再加进val
}
swap(num[u[p].ind],u[p].val);
}
inline void Print(register int x){
if (x>=10ll) Print(x/10ll);
putchar(x%10ll+48ll);
}
inline void print(register int x,const char ch){
if (x<0){x=-x,putchar('-');}
if (x==0){putchar('0');putchar(ch);return ;}
Print(x);putchar(ch);
}
int main(){
int n=read(),m=read();
const int Size=pow(n,(double)0.666666666);
for (register int i=1;i<=n;++i){
num[i]=read();
}
for (register int i=1;i<=m;++i){
char opr=gc();
if (opr=='Q') q[++cntq]=Query{read(),read(),cntq,cntu};
else u[++cntu]=Update{read(),read()};
}
for (register int i=1;i<=n;++i){
pos[i]=(i-1)/Size+1;
}
sort(q+1,q+1+cntq);
register int l=1,r=0;
register int p=0;//修改的操作
for (register int i=1;i<=m;++i){
while (l<q[i].l) Del(num[l++]);
while (l>q[i].l) Add(num[--l]);
while (r<q[i].r) Add(num[++r]);
while (r>q[i].r) Del(num[r--]);
while (p<q[i].last) Upd(++p,i);
while (p>q[i].last) Upd(p--,i);
Ans[q[i].id]=ans;
}
for (register int i=1;i<=cntq;++i){
print(Ans[i],'\n');
}
}

树上莫队

普通莫队是在一个一个地移动指针,树上莫队是一个一个爬节点—-SXYZ巨佬

例题8

BZOJ苹果树

这才是真的树上莫队。

题解

例题9

SP10707 COT2 - Count on a tree II

和上面那题几乎一样,这里只放代码:

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXM 17
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
vector<int>G[MAXN];
inline void AddEdge(int u,int v){
G[u].push_back(v);
}
int c[MAXN];//每个点的颜色
int anc[MAXN][MAXM],dep[MAXN];
int euler[MAXN];//欧拉序(出栈入栈都要记录)
int L[MAXN],R[MAXN];//左右端点
int tot;
void dfs(int u,int father){
dep[u]=dep[father]+1;
anc[u][0]=father;
euler[L[u]=++tot]=u;
for (register int i=1;i<MAXM;++i) anc[u][i]=anc[anc[u][i-1]][i-1];
for (register int i=0;i<G[u].size();++i){
int v=G[u][i];
if (v!=father) dfs(v,u);
}
euler[R[u]=++tot]=u;
}
inline int LCA(int u,int v){
if (dep[u]<dep[v]) swap(u,v);
for (register int i=MAXM-1;i>=0;--i){
if (dep[anc[u][i]]>=dep[v]) u=anc[u][i];
}
if (u==v) return u;
for (register int i=MAXM-1;i>=0;--i){
if (anc[u][i]!=anc[v][i]){
u=anc[u][i],v=anc[v][i];
}
}
return anc[u][0];
}

int n,m;
inline void discrete(){
int tempc[MAXN];
for (register int i=1;i<=n;++i) tempc[i]=c[i];
sort(tempc+1,tempc+1+n);
for (register int i=1;i<=n;++i){
c[i]=lower_bound(tempc+1,tempc+1+n,c[i])-tempc;
}
}

int b[MAXN];//块编号
struct Query{
int u,v,lca,id;
}q[MAXN];
inline bool operator < (const Query &A,const Query &B){//莫队的玄学优化
return (b[A.u]^b[B.u])?b[A.u]<b[B.u]:((b[A.u]&1)?A.v<B.v:A.v>B.v);
}
int inq[MAXN];//在不在莫队维护的范围内
int ans,cnt[MAXN];
inline void Update(int i){//相应地加上/减去元素
if (!inq[i]){//加上
cnt[c[i]]++;
if (cnt[c[i]]==1) ans++;
inq[i]=true;
}
else {
cnt[c[i]]--;
if (cnt[c[i]]==0) ans--;
inq[i]=false;
}
}
int Ans[MAXN];
inline Query make_q(int u,int v,int lca,int id){
Query temp;
temp.id=id;
temp.u=u,temp.v=v;
temp.lca=lca;
return temp;
}
int main(){
n=read(),m=read();int Size=sqrt(n);//块大小
for (register int i=0;i<MAXN;++i){
b[i]=i/Size+1;
}
for (register int i=1;i<=n;++i){
c[i]=read();
}
discrete();
for (register int i=1;i<n;++i){
int u=read(),v=read();
AddEdge(u,v);
AddEdge(v,u);
}
dfs(1,1);
for (register int i=1;i<=m;++i){
int u=read(),v=read();
if (L[u]>L[v]) swap(u,v);//保证这条链是从左往右
int lca=LCA(u,v);
if (u==lca) q[i]=make_q(L[u],L[v],0,i);//u为这条链的顶点
else q[i]=make_q(R[u],L[v],lca,i);
}
sort(q+1,q+1+m);
int l=1,r=0;//模仿STL队列
for (register int i=1;i<=m;++i){
while (l<q[i].u) Update(euler[l++]);
while (l>q[i].u) Update(euler[--l]);
while (r<q[i].v) Update(euler[++r]);
while (r>q[i].v) Update(euler[r--]);
if (q[i].lca) Update(q[i].lca);//注意处理lca
Ans[q[i].id]=ans;
if (q[i].lca) Update(q[i].lca);
}
for (register int i=1;i<=m;++i){
printf("%d ",Ans[i]);
}
}

回滚莫队

回滚莫队这个名字好可爱呀!

有时候加上一个元素可以$O(1)$算出答案,但是减去一个元素不能$O(1)$算出,而一些加上或者减去时间复杂度$O(\log n)$的算法会被卡成狗,此时回滚莫队就派上用场了。

事实上就是$l$端点移动的部分每一次都重新计算。

分只增不减和只减不增两个种类。

例题10

AT1219 歴史の研究

回滚莫队的基础题。

题解

例题11

BZOJ 4358 permu

我的解法绝对是全网最易懂的。

题解

例题12

P4137 Rmq Problem / mex

虽然权值线段树也是可做的。

只减不增的回滚莫队(虽然我智障写了一个只增不减的版本)

题解

例题13

SP20644 ZQUERY - Zero Query

另一种鬼畜的莫队套路。

题解

分块+莫队

分块$O(\sqrt n)$的怎么会跑得比$O(\log n)$的线段树/树状数组快?

结合莫队算法的特性,发现有时候使用分块+莫队会使得复杂度少一个$\log$避免被卡。

例题14

P4867 Gty的二逼妹子序列

洛谷数据水,$O(n \sqrt n \log n)$的做法也可以卡过。

但是这个就是一个$\log $的差距:

题解

例题15

P4396 [AHOI2013]作业

一样的套路呀

题解

总结:莫队是一种扩展性极强的算法,而且常数小极难被卡,缺点是必须在线,强制在线就gg了(虽然有在线莫队这种东西)。掌握还是非常必要的。

 评论