莫队专题

自用笔记算法

莫队专题

莫队算法是用来解决一类没有修改操作 只有查询操作的离线区间问题
有曼哈顿距离最小生成树和分块两种写法 本篇博客均采用后者
不同的题目只需修改add和del函数即可

cf 617E

题目要求

1e5个数字 1e5次询问
每次询问i-j的区间内有多少对数字满足ai^ai+1^···^aj=k

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 2000000
#define mm(a,b) memset(a,0,sizeof(b)) 
#define LL long long
using namespace std;
LL gcd(LL a,LL b){if(b==0) return a;return gcd(b,a%b);}
int n,m,k;
LL flag[maxn],Ans,ans[maxn];
int a[maxn],pos[maxn]; 
struct node{
	int l,r,id;
}q[maxn];
bool cmp(node a,node b){
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void add(int x){
	Ans+=flag[a[x]^k];
	flag[a[x]]++;
}
void del(int x){
	flag[a[x]]--;
	Ans-=flag[a[x]^k];
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d%d",&n,&m,&k);
	mm(ans,0),mm(pos,0),mm(flag,0);
	int l=1,r=0;
	flag[0]=1,Ans=0;
	int block=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		a[i]^=a[i-1];
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++){
		while(q[i].l<l){
			l--;
			add(l-1);
		}
		while(q[i].l>l){
			del(l-1);
			l++;
		}
		while(q[i].r<r){
			del(r);
			r--;
		}
		while(q[i].r>r){
			r++;
			add(r);
		}
		ans[q[i].id]=Ans;
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}

思路

本题是莫队算法模版题
异或前缀和
需要注意的几个地方
1 结果可能爆int
2 区间[i,j]的异或和是sum[i-1]^sum[j]的结果，所以要保存i-1到j的异或值(正常的莫队模版前2个while中l改为l-1)
3 l和r以及flag[0]的初值,flag[i]代表前缀和的数量
4 add()和dele()函数的写法：add(x)可以转换成num^a[x]=k中num的个数

bzoj 2038

题目要求

有n只袜子 每只袜子有一种颜色 m次询问
每次询问i-j区间内任意取2只袜子 相同颜色的概率是多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 50050
#define mm(a,b) memset(a,0,sizeof(b)) 
#define LL long long
using namespace std;
LL gcd(LL a,LL b){if(b==0) return a;return gcd(b,a%b);}
int n,m;
LL flag[maxn],Ans;
int a[maxn],pos[maxn]; 
struct query{
	int l,r,id;
}q[maxn];
struct Answer{
	LL a,b;
}ans[maxn];
bool cmp(query a,query b){
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void add(int x){
	Ans-=flag[a[x]]*flag[a[x]];
	flag[a[x]]+=1;
	Ans+=flag[a[x]]*flag[a[x]];
}
void del(int x){
	Ans-=flag[a[x]]*flag[a[x]];
	flag[a[x]]-=1;
	Ans+=flag[a[x]]*flag[a[x]];
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	mm(pos,0),mm(flag,0);
	int l=1,r=0;
	flag[0]=1,Ans=0;
	int block=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	for(int i=1;i<=m;i++){
		while(q[i].l<l){
			l--;
			add(l);
		}
		while(q[i].l>l){
			del(l);
			l++;
		}
		while(q[i].r<r){
			del(r);
			r--;
		}
		while(q[i].r>r){
			r++;
			add(r);
		}
		LL temp1=Ans-(q[i].r-q[i].l+1);
		LL temp2=(LL)(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
		LL temp=gcd(temp1,temp2);
		ans[q[i].id].a=temp1/temp;
		ans[q[i].id].b=temp2/temp;
	}
	for(int i=1;i<=m;i++) printf("%lld/%lld\n",ans[i].a,ans[i].b);
	return 0;
}

思路

裸的莫队
首先对于一个[l，r]的询问，设flag[i]表示第i种颜色在这一区间内出现的个数，那么随机抽到相同一对的概率就是
∑C(flag[i],2)/C(r-l+1,2)
然后有：∑(flag[i]^2-flag[i])/((r-l+1)*(r-l))
最后对分子分母同除gcd即可
add和del函数：减去该颜色的flag平方+更新后现在的flag平方
区间内减去所有颜色的flag相当于间区该区间的长度

cf 633h

题目要求

给你n个数，然后有q次询问
每次询问给你l,r区间
你首先得把l,r区间的数全部拿出来，从小到大排序，然后再去重
然后答案就等于ans = f[1]×a[1]+f[2]×a[2]….+f[n]×a[n]
其中f[i]是第i个fib数
要求答案mod m

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 30050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,mod,q; 
int last[maxn],f[maxn],l[maxn],r[maxn],ans[maxn],step[maxn];
pair<int,int>a[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&mod);
	mm(last,-1),mm(f,0),mm(ans,0),mm(step,0);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].first);
		a[i].second=i;
	}
	sort(a+1,a+1+n);
	scanf("%d",&q);
	for(int i=1;i<=q;i++) scanf("%d%d",&l[i],&r[i]);
	f[1]=1,f[2]=1;
	for(int i=3;i<=n;i++) f[i]=(f[i-1]+f[i-2])%mod;
	for(int i=1;i<=n;i++){
		int data=a[i].first;
		int po=a[i].second;
		for(int j=1;j<=q;j++){
			if(po<l[j] || po>r[j]) continue;
			if(data==last[j]) continue;
			ans[j]=(ans[j]+(data%mod)*f[++step[j]])%mod;
			last[j]=data;
		}
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	return 0;
}

思路

本题的正解是莫队+线段树 但由于常数太大跑得还没有暴力快 这里给出暴力的思路
把所有的数字从小到大排序 并记录下原始的位置
对于每个数字暴力对每个询问的贡献
last用来记录该询问的上一个数字 用来判重
step用来记录每个询问访问到第几个fib数
由于ai可以取到0 所以last初始化-1

HDU 4676

题目要求

给你n个数，然后Q次询问，每次问你l,r区间的两两之间的GCD和是多少

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 20050
#define LL long long 
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,k,block;
LL Ans;
LL ans[maxn],flag[maxn],phi[maxn];
int a[maxn],pos[maxn];
vector<int>factor[maxn];
struct query{
	int l,r;
	int id;
}q[maxn];
void init(){
	for(int i=1;i<maxn;i++){
		for(int j=i;j<maxn;j+=i) factor[j].push_back(i);
	}
	phi[1]=1;
	for(int i=2;i<maxn;i++){
		if(!phi[i]){
			for(int j=i;j<maxn;j+=i){
				if(!phi[j]) phi[j]=j;
				phi[j]=phi[j]*(i-1)/i;
			}
		}
	}
}
bool cmp(query a,query b){
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void add(int x){
    for(auto p:factor[a[x]]) Ans+=flag[p]*phi[p];
    for(auto p:factor[a[x]]) flag[p]++;
}
void del(int x){
    for(auto p:factor[a[x]]) flag[p]--;
    for(auto p:factor[a[x]]) Ans-=flag[p]*phi[p];
}
void solve(){
	int l=1,r=0;
	flag[0]=1,Ans=0;
	for(int i=1;i<=k;i++){
		while(q[i].l<l){
			l--;
			add(l);
		}
		while(q[i].l>l){
			del(l);
			l++;
		}
		while(q[i].r<r){
			del(r);
			r--;
		}
		while(q[i].r>r){
			r++;
			add(r);
		}
		ans[q[i].id]=Ans;
	}
}
int Case=1;
int main(){
//	freopen("input.txt","r",stdin);
	init();
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		mm(pos,0),mm(ans,0),mm(flag,0);
		block=sqrt(n);
		scanf("%d",&k);
		for(int i=1;i<=k;i++){
			scanf("%d%d",&q[i].l,&q[i].r);
			q[i].id=i;
			pos[i]=(i-1)/block+1;
		}
		sort(q+1,q+1+k,cmp);
		solve();
		printf("Case #%d:\n",Case++);
		for(int i=1;i<=k;i++) printf("%lld\n",ans[i]);
	}
	return 0;
}

思路

转跳链接
公式推导如上 flag记录l到r区间内d的倍数
然后就是裸的莫队了

bzoj 3809

题目要求

Autumn和Bakser又在研究Gty的妹子序列了！但他们遇到了一个难题。
对于一段妹子们，他们想让你帮忙求出这之内美丽度∈[a,b]的妹子的美丽度的种类数。
为了方便，我们规定妹子们的美丽度全都在[1,n]中。
给定一个长度为n(1<=n<=100000)的正整数序列s(1<=si<=n)，对于m(1<=m<=1000000)次询问“l,r,a,b”，每次输出sl…sr中，权值∈[a,b]的权值的种类数。

第一行包括两个整数n,m(1<=n<=100000,1<=m<=1000000),表示数列s中的元素数和询问数。
第二行包括n个整数s1…sn(1<=si<=n)。
接下来m行,每行包括4个整数l,r,a,b(1<=l<=r<=n,1<=a<=b<=n),意义见题目描述。
保证涉及的所有数在C++的int内。
保证输入合法。

对每个询问，单独输出一行，表示sl…sr中权值∈[a,b]的权值的种类数。

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m,num,block;
int l[maxn],r[maxn],belong[maxn];
int a[maxn],c[maxn],flag[maxn],ans[maxn*10],pos[maxn];
struct query{
	int l,r;
	int a,b;
	int id;
}q[maxn*10];
bool cmp(query a,query b){
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void build(){
    block=sqrt(n);
    num=n/block;
	if(n%block) num++;
    for(int i=1;i<=num;i++) l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++) belong[i]=(i-1)/block+1;
}
void add(int x){
	c[a[x]]++;
	if(c[a[x]]==1) flag[belong[a[x]]]++;
}
void del(int x){
	c[a[x]]--;
	if(c[a[x]]==0) flag[belong[a[x]]]--;
}
int query(int L,int R){
	int re=0;
    if(belong[L]==belong[R]){
        for(int i=L;i<=R;i++){
            if(c[i]) re++;
        }
    }
    else{
        for(int i=belong[L]+1;i<=belong[R]-1;i++) re+=flag[i];
        for(int i=L;i<=r[belong[L]];i++){
            if(c[i]) re++;
        }
        for(int i=l[belong[R]];i<=R;i++){
            if(c[i]) re++;
        }
    }
    return re;
}
void solve(){
	int l=1,r=0;
	flag[0]=1;
	for(int i=1;i<=m;i++){
		while(q[i].l<l){
			l--;
			add(l);
		}
		while(q[i].l>l){
			del(l);
			l++;
		}
		while(q[i].r<r){
			del(r);
			r--;
		}
		while(q[i].r>r){
			r++;
			add(r);
		}
		ans[q[i].id]=query(q[i].a,q[i].b);
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	build();
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d%d",&q[i].l,&q[i].r,&q[i].a,&q[i].b);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	solve();
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

思路

不带修改的离线查询 自然联想到莫队
如果用树状数组或者线段树查询维护颜色 带log的复杂度可能会爆 所以我们考虑分块
数组c记录每种颜色出现的次数 flag相当于每种颜色所在块的lazy 记录该块出现不同数字的个数
add和del函数：若该颜色第一次出现 该块lazy++ 若颜色全部删掉 该块lazy–
注意：
1.两次分块 莫队的分块是针对下标分块 正常的跑o1的修改 而build里的分块是针对颜色分块
2.注意两次分块的pos和belong数组 由于本题颜色的范围也是1到n 所以可以只用一个数组 但若范围不一样 则分块的数组必须分开
为了更严谨 本题的数组分开写的
3.由于本题的内存卡的比较紧 我们只对q和ans的数组额外对开10倍 注意ans也要多开10倍

bzoj 3339

题目要求

n个数字 m次询问
每次给出区间l到r 询问不在l到r区间内的最小数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 200050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int a[maxn],flag[maxn],pos[maxn],ans[maxn];
int n,m,Ans;
struct query{
	int l,r;
	int id;
}q[maxn];
bool cmp(query a,query b){
	if(pos[a.l]==pos[b.l]) return a.r<b.r;
	return pos[a.l]<pos[b.l];
}
void add(int x){
	flag[a[x]]++;
	if(Ans==a[x]){
		while(flag[Ans]) Ans++;
	}
}
void del(int x){
	flag[a[x]]--;
	if(flag[a[x]]==0 && a[x]<Ans) Ans=a[x];
}
void solve(){
	int l=1,r=0;
	Ans=0;
	for(int i=1;i<=m;i++){
		while(q[i].l<l){
			l--;
			add(l);
		}
		while(q[i].l>l){
			del(l);
			l++;
		}
		while(q[i].r<r){
			del(r);
			r--;
		}
		while(q[i].r>r){
			r++;
			add(r);
		}
		ans[q[i].id]=Ans;
	}
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&m);
	int block=sqrt(n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		pos[i]=(i-1)/block+1;
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
	}
	sort(q+1,q+1+m,cmp);
	solve();
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

思路

直接莫队暴力就好了
add和del函数：flag记录某个数字出现的次数
若前一状态的Ans等于该数字 ++到数字没有出现过为止
若该数字全部删掉 维护一下Ans的最小值即可
注意：
本题的数字是从0开始的 若flag[0]不能跟之前一样初始化为1

cf 620F

题目要求

n个数字 m次询问
每次给出区间l到r 在l和r内挑出两个数字a和b 假设a小b大 求所有二元组 a xor a+1 xor···xor b的最大值

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1000050
#define mm(a,b) memset(a,b,sizeof(a))
using namespace std;
int n,m;
int a[maxn],l[maxn],r[maxn],pre[maxn],b[maxn],ans[maxn];
int main(){
//	freopen("input.txt","r",stdin);
	for(int i=1;i<maxn;i++) pre[i]=pre[i-1]^i;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d%d",&l[i],&r[i]);
	for(int i=1;i<=n;i++){
		int Max=0;
		for(int j=i;j<=n;j++){
			if(a[i]<=a[j]) Max=max(Max,pre[a[i]-1]^pre[a[j]]);
			else Max=max(Max,pre[a[j]-1]^pre[a[i]]);
			b[j]=Max;
		}
		for(int j=1;j<=m;j++){
			if(i>=l[j] && i<=r[j]) ans[j]=max(ans[j],b[r[j]]);
		}
	}
	for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
	return 0;
}

思路

正解是莫队+trie 不会 但是n方暴力可以过
基本想法就是，离线算法，计算每个(i,j)的最大值，再更新所有查询的ans
但是呢，如果朴素的计算每个(i,j)，复杂度要O(n^3)是不行的。
n三方降到n平方使用前缀和
我们注意到，实际我们需要计算的只有对任意a[i]和a[j]（设min(a[i], a[j]) = x, max(a[i], a[j]) = y）
f(x, y)这个单独计算每一组预处理之后是O(1)的，所以呢我们只需要枚举i, j即可算出所有这样的f(x, y)，复杂度是O(n ^ 2)
然后，由于我们存不下这么多对的解，所以要考虑如何更新ans了，这里有点dp的想法
dp(i,j)表示，在[i, j]区间内，必须用到i的最大值
dp二维降到一维用滚动数组 压掉i这一维
对于第j组的查询，L[j], R[j], ans[j] = max(dp(i, R[j]) ) 其中L[j] <= i <= R[j]
注意pre数组要开100w

本文标题:莫队专题

文章作者:Hippopmonkey

发布时间:2017-09-28, 00:19:26

最后更新:2017-10-01, 10:31:56

原始链接:http://xuboming8.github.io/2017/09/28/莫队专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 莫队专题
    1. 1.1. cf 617E
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
    2. 1.2. bzoj 2038
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. cf 633h
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
    4. 1.4. HDU 4676
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. bzoj 3809
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. bzoj 3339
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. cf 620F
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
      3. 1.7.3. 思路
|