莫队
关于莫队算法
普通莫队
带修莫队
树上莫队
回滚莫队
大致分为这4类莫队算法
莫队算法——优雅而不失复杂度的暴力
莫队算法是一种像暴力一样好写，同时具有分块算法时间复杂度的技巧。其特点是常数较小，适合离线处理问题。
如果从 \([l, r]\) 的答案能够在 \(O(1)\) 时间内扩展到 \([l+1, r]\)、\([l-1, r]\)、\([l,
r+1]\)、\([l, r-1]\)（即与 \([l, r]\)
相邻的区间）的答案，那么使用莫队算法可以在 \(O(n\sqrt{n})\)
的复杂度内求出所有询问的答案。
莫队算法基本原理
双指针跳跃
如下图所示，假如我们要求 \(Q_2\)
的区间和，并且已经得到了 \(Q_1\)
的区间和：
图示说明双指针跳跃原理
- 将 \(Q_1\)
的右指针右移，沿路累加经过的数值，得到区间 \([1, 15]\) 的区间和。
- 然后将 \(Q_1\)
的左指针右移，沿路减去经过的数值，得到区间 \([6, 15]\) 的区间和。
同理，从 \(Q_2\) 到 \(Q_1\) 也是如此（右移变为左移）。
我们称操作 1 为加入操作，操作 2
为删除操作。
在莫队算法中，加入和删除操作是解决问题的核心。
具体实现
定义状态
假设我们当前在区间 \([l,
r]\)：
- 用 \(vis[i]\) 表示当前区间中数字
\(i\) 出现的次数。
- 如果某个 \(i\) 的 \(vis[i]\) 超过
1，则当前区间不满足互不相同的条件。
- 用一个计数器 \(sum\) 表示当前区间中
\(vis[i] > 1\) 的数字的个数。
- 如果 \(sum \neq
0\)，表示当前区间不满足互不相同的条件。
加入操作
每加入一个数 \(i\)：
1. \(vis[i] += 1\)。
2. 如果 \(vis[i]\) 从 1 变为超过 1，则
\(sum += 1\)。
删除操作
每删除一个数 \(i\)：
1. \(vis[i] -= 1\)。
2. 如果 \(vis[i]\) 从超过 1 变为 1，则
\(sum -= 1\)。
判断结果
在移动到指定区间后：
- 如果 \(sum > 0\)，输出
No。
- 如果 \(sum = 0\)，输出
Yes。
1
2
| void add(int x){if(vis[v[x]]==1)ans++;vis[v[x]]++;}
void remove(int x){vis[v[x]]--;if(vis[v[x]]==1)ans--;}
|
1
2
3
4
5
6
7
8
9
10
| l=1;r=0;
for(int i=1;i<=m;i++){
while(l>a[i].l)add(--l);
while(l<a[i].l)remove(l++);
while(r<a[i].r)add(++r);
while(r>a[i].r)remove(r--);
if(ans==0)a[i].ans=0;
else a[i].ans=1;
}
|
莫队中要注意的细节——指针移动
首先可以明确一点：
左指针向左移是加入操作，向右移是删除操作
右指针向左移是删除操作，向右移是加入操作
加入操作是先移动指针，再将指向的值加入
而删除是先将指针所指的值删除，再将指针移动
刚开始的区间是[1,0]，可以发现很奇怪啊
不应该l<=r吗，怎么l>r
我们可以用前缀和的思想想一下
l代表什么？代表[0,l)的位置都删除过了
r代表什么？代表[0,r]的位置都加入过了
那么代入l=1,r=0正好就是区间[0,0]，也就是什么都没有。
那就可以解释得通了！
明显，如果我们按询问区间这样暴力去跳左右指针，是可以被卡的
复杂度\(O(n\sqrt{n}\))
算法流程：
我们将长度为n的序列分成O(\(\sqrt{n}\))块，从1至\(\sqrt{n}\)编号。
然后标记每一个点所属的块block[i](表示i点属于块的编号)
然后我们对询问排序：
先按左端点所在的块编号为第一关键字排序
如果相同，则按右端点的位置排序
然后按排序后的顺序处理每一个询问，求得答案
再通过一次排序复原原来的顺序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| bool cmp1(kkk a,kkk b){return a.id<b.id;}
bool cmp(kkk a,kkk b){
if(blo[a.l]!=blo[b.l])return a.l<b.l;
else return a.r<b.r;
}
block=sqrt(n);
for(int i=1;i<=n;i++)
blo[i]=(i-1)/block+1;
for(int i=1;i<=m;i++)
{
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
sort(a+1,a+m+1,cmp1);
|
莫队的优化
对于左端点在同一奇数(编号)块时，右端点按升序排序，在同一偶数(编号)块时，右端点按降序排序。
1
2
3
4
5
6
| bool cmp(kkk a,kkk b)
{
if(blo[a.l]!=blo[b.l])return a.l<b.l;
if(blo[a.l]%2==0)return a.r>b.r;
return a.r<b.r;
}
|
据数据结构神lxl大佬说，普通莫队将块大小调节成\(n/\sqrt{m}\) 会块。
[国家集训队] 小 Z 的袜子
题目描述
upd on 2020.6.10 ：更新了时限。
作为一个生活散漫的人，小 Z
每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z
再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 \(N\) 只袜子从
\(1\) 到 \(N\) 编号，然后从编号 \(L\) 到 \(R\) 的袜子中随机选出两只来穿。尽管小 Z
并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小
Z 希望这个概率尽量高，所以他可能会询问多个 \((L,R)\) 以方便自己选择。
然而数据中有 \(L=R\)
的情况，请特判这种情况，输出0/1。
输入格式
输入文件第一行包含两个正整数 \(N\)
和 \(M\)。\(N\) 为袜子的数量，\(M\) 为小 Z 所提的询问的数量。接下来一行包含
\(N\) 个正整数 \(C_i\)，其中 \(C_i\) 表示第 \(i\)
只袜子的颜色，相同的颜色用相同的数字表示。再接下来 \(M\) 行，每行两个正整数 \(L, R\) 表示一个询问。
输出格式
包含 \(M\)
行，对于每个询问在一行中输出分数 \(A/B\) 表示从该询问的区间 \([L,R]\)
中随机抽出两只袜子颜色相同的概率。若该概率为 \(0\) 则输出 0/1，否则输出的
\(A/B\)
必须为最简分数。（详见样例）
样例 #1
样例输入 #1
1
2
3
4
5
6
| 6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6
|
样例输出 #1
提示
\(30\%\) 的数据中，\(N,M\leq 5000\)；
\(60\%\) 的数据中，\(N,M \leq 25000\)；
\(100\%\) 的数据中，\(N,M \leq 50000\)，\(1 \leq L < R \leq N\)，\(C_i \leq N\)。
假设此时有x对颜色为a的袜子，那么取到一对a的方案数是a(a−1)
很显然吧
那么加入1只颜色为a的袜子，我们把原来取一对颜色a的方案数减掉，然后更新a的数量
再把取一对颜色a的方案数加回去
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
| #include<bits/stdc++.h>
#define maxn 100001
using namespace std;
struct kkk
{
long long l,r,id,a,b;
}a[maxn];
long long ans,ansl[maxn],ansr[maxn],gcd1;
int blo[maxn],block,n,m,l,r,tag[maxn],v[maxn];
bool cmp1(kkk a,kkk b)
{return a.id<b.id;}
bool cmp(kkk a,kkk b)
{
if(blo[a.l]!=blo[b.l])return a.l<b.l;
if(blo[a.l]%2==0)return a.r>b.r;
return a.r<b.r;
}
void add(int x){ans-=tag[v[x]]*(tag[v[x]]-1);tag[v[x]]++;ans+=tag[v[x]]*(tag[v[x]]-1);}
void remove(int x){ans-=tag[v[x]]*(tag[v[x]]-1);tag[v[x]]--;ans+=tag[v[x]]*(tag[v[x]]-1);}
int main()
{
cin>>n>>m;
block=n/sqrt(m);
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=1;i<=n;i++)blo[i]=(i-1)/block+1;
for(int i=1;i<=m;i++){
cin>>a[i].l>>a[i].r;
a[i].id=i;
}
sort(a+1,a+m+1,cmp);
l=1;r=0;
for(int i=1;i<=m;i++){
while(l>a[i].l)add(--l);
while(l<a[i].l)remove(l++);
while(r<a[i].r)add(++r);
while(r>a[i].r)remove(r--);
if(a[i].l==a[i].r)
{
ansl[i]=0;ansr[i]=1;
a[i].a=ansl[i];a[i].b=ansr[i];
continue;
}
ansl[i]=ans;
ansr[i]=(a[i].r-a[i].l+1)*(a[i].r-a[i].l);
gcd1=__gcd(ansl[i],ansr[i]);
ansl[i]/=gcd1;ansr[i]/=gcd1;
a[i].a=ansl[i];a[i].b=ansr[i];
}
sort(a+1,a+m+1,cmp1);
for(int i=1;i<=m;i++)
cout<<a[i].a<<'/'<<a[i].b<<'\n';
}
|
小B的询问
题目描述
小B 有一个长为 \(n\) 的整数序列
\(a\)，值域为 \([1,k]\)。
他一共有 \(m\)
个询问，每个询问给定一个区间 \([l,r]\)，求：
\[\sum\limits_{i=1}^k c_i^2\]
其中 \(c_i\) 表示数字 \(i\) 在 \([l,r]\) 中的出现次数。
小B请你帮助他回答询问。
输入格式
第一行三个整数 \(n,m,k\)。
第二行 \(n\) 个整数，表示 小B
的序列。
接下来的 \(m\) 行，每行两个整数
\(l,r\)。
输出格式
输出 \(m\)
行，每行一个整数，对应一个询问的答案。
样例 #1
样例输入 #1
1
2
3
4
5
6
| 6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
|
样例输出 #1
提示
【数据范围】
对于 \(100\%\) 的数据，\(1\le n,m,k \le 5\times 10^4\)。
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
| #include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int cnt[N],a[N],ans=0;
struct Que{
int l,r,id;
}que[N];
int T,Ans[N];
bool cmp(Que a,Que b){
if(a.l/T!=b.l/T) return a.l/T<b.l/T;
return a.r<b.r;
}
void add(int x){
ans-=cnt[x]*cnt[x];
cnt[x]++;
ans+=cnt[x]*cnt[x];
}
void del(int x){
ans-=cnt[x]*cnt[x];
cnt[x]--;
ans+=cnt[x]*cnt[x];
}
int n,m,k;
int main(){
cin>>n>>m>>k;
T=sqrt(n);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++) cin>>que[i].l>>que[i].r,que[i].id=i;
sort(que+1,que+1+m,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(r<que[i].r) add(a[++r]);
while(r>que[i].r) del(a[r--]);
while(l>que[i].l) add(a[--l]);
while(l<que[i].l) del(a[l++]);
Ans[que[i].id]=ans;
}
for(int i=1;i<=m;i++) cout<<Ans[i]<<endl;
}
|
带修莫队
[国家集训队] 数颜色 / 维护队列
题目描述
墨墨购买了一套 \(N\)
支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会向你发布如下指令：
\(Q\ L\ R\) 代表询问你从第 \(L\) 支画笔到第 \(R\)
支画笔中共有几种不同颜色的画笔。
\(R\ P\ C\) 把第 \(P\) 支画笔替换为颜色 \(C\)。
为了满足墨墨的要求，你知道你需要干什么了吗？
输入格式
第 \(1\) 行两个整数 \(N\)，\(M\)，分别代表初始画笔的数量以及墨墨会做的事情的个数。
第 \(2\) 行 \(N\) 个整数，分别代表初始画笔排中第 \(i\) 支画笔的颜色。
第 \(3\) 行到第 \(2+M\)
行，每行分别代表墨墨会做的一件事情，格式见题干部分。
输出格式
对于每一个 Query 的询问，你需要在对应的行中给出一个数字，代表第 \(L\) 支画笔到第 \(R\) 支画笔中共有几种不同颜色的画笔。
样例 #1
样例输入 #1
1
2
3
4
5
6
7
| 6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
|
样例输出 #1
提示
对于30%的数据，\(n,m \leq
10000\)
对于60%的数据，\(n,m \leq
50000\)
对于所有数据，\(n,m \leq
133333\)
所有的输入数据中出现的所有整数均大于等于 \(1\) 且不超过 \(10^6\)。
本题可能轻微卡常数
来源：bzoj2120
本题数据为洛谷自造数据，使用 CYaRon
耗时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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
| #include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int T;
struct Que
{
int l,r,id,tim;
}que[N];
int as[N];
bool cmp(Que a,Que b)
{
if(a.l/T==b.l/T)
{
if(a.r/T==b.r/T) return a.tim<b.tim;
return a.r/T<b.r/T;
}
return a.l/T<b.l/T;
}
struct Upd{
int p,col;
}upd[N];
int cnt[N],ans=0,a[N];
void add(int x)
{
if(!cnt[x]) ans++;
cnt[x]++;
}
void del(int x)
{
cnt[x]--;
if(!cnt[x]) ans--;
}
int n,m,iq=0,ic=0;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++)
{
char opt;
int l,r;
cin>>opt>>l>>r;
if(opt=='Q') que[++iq]={l,r,iq,ic};
else upd[++ic]={l,r};
}
T=pow(n,0.666);
sort(que+1,que+1+iq,cmp);
int l=1,r=0,now=0;
for(int i=1;i<=m;i++)
{
while(l<que[i].l) del(a[l++]);
while(l>que[i].l) add(a[--l]);
while(r>que[i].r) del(a[r--]);
while(r<que[i].r) add(a[++r]);
while(now<que[i].tim)
{
++now;
int p=upd[now].p,c=upd[now].col;
if(l<=p&&p<=r) del(a[p]),add(c);
swap(a[p],upd[now].col);
}
while(now>que[i].tim){
int p=upd[now].p,c=upd[now].col;
if(l<=p&&p<=r) del(a[p]),add(c);
swap(a[p],upd[now].col);
now--;
}
as[que[i].id]=ans;
}
for(int i=1;i<=iq;i++) cout<<as[i]<<endl;
}
|
