【学习笔记】分块&莫队

发表于

分块&莫队

分块：

如果我们把每m个元素分为一块，共有n/m块，每次区间加的操作会涉及O(n/m)个整块，以及区间两侧两个不完整的块中至多2m个元素。每次操作的复杂度是O(n/m)+O(m)，根据均值不等式，当m取√n时总复杂度最低。(hzwer)

分块：

1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;++i){
	bl[i]=(i-1)/blk+1;
}
nb=bl[n];
for(int i=1;i<=nb;++i){
	lblk[i]=(i-1)*blk+1;
	rblk[i]=i*blk;
}
rblk[nb]=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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL 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^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=1000+8;
int n,b;
int x,y;
int nume,head[N];
struct edge{
	int to,nxt;
}e[N<<1];
IL void add_edge(int x,int y)
{
	e[++nume]=(edge){y,head[x]};head[x]=nume;
}
int k,bl[N],ct[N];
//vector<int> s[N];
int num,st[N];
IL void dfs(int x,int fa)
{
	int tmp=num;
	for(int i=head[x];i;i=e[i].nxt){
		int to=e[i].to;
		if(to!=fa){
			dfs(to,x);
			if(num-tmp>=b){
				++k;
				ct[k]=x;
				while(num>tmp){
					//s[k].pb(st[num]);
					bl[st[num]]=k;
					--num;
				}
			}
		}
	}
	st[++num]=x;
}
int main()
{
	n=io;b=io;
	for(int i=1;i<n;++i){
		x=io;y=io;
		add_edge(x,y);
		add_edge(y,x);
	}
	dfs(1,0);
	//if(!num)	ct[++num]=1; 
	while(num>0){
		//s[k].pb(st[num]);
		bl[st[num]]=k;
		--num;
	}
	printf("%d\n",k);
	for(int i=1;i<=n;++i){
		printf("%d ",bl[i]);
	}
	printf("\n");
	for(int i=1;i<=k;++i){
		printf("%d ",ct[i]);
	}
	return 0;
}

莫队：

普通莫队、带修改莫队、树上莫队、回滚莫队（见全网最详细、最深的四类莫队算法讲解）
普通莫队：
先按左指针所在块升序，同一块按右指针升序。
复杂度：设块长m，共n/m块，左指针移动q·m次，右指针移动n·n/m次，m取n/sqrt(q)时，为n·sqrt(q)

莫队：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int curl=1,curr=0; 
for(int i=1;i<=qn;++i){
	while(curl<b[i].l){
		remove(curl);++curl;
	}
	while(curl>b[i].l){
		--curl;add(curl);
	}
	while(curr<b[i].r){
		++curr;add(curr);
	}
	while(curr>b[i].r){
		remove(curr);--curr;
	}
	solve(i);
}

把块大小blk设成定值不易出错，方便调块大小卡常。

luogu4396 [AHOI2013]作业
莫队+分块：在区间上莫队，在值域上分块。莫队的转移是O(1)。每个询问求答案是用分块，复杂度根号，查询的总复杂度为q根号n。总复杂度是O(n·sqrt(q)+q·sqrt(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
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>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL 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^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,QN=1000000+8,NB=350;
const int blk=300;
int n,qn;
int a[N];
struct ques{
	int l,r,a,b,id;
}b[QN];
int bl[N],nb,lblk[NB],rblk[NB];//值域也是1到n，共用一个bl 
IL bool cmp(const ques &a,const ques &b)
{
	if(bl[a.l]!=bl[b.l])	return bl[a.l]<bl[b.l];
	return a.r<b.r;
}	
int cnt[N],num1[NB],num2[NB];
IL void add(int x)
{
	++cnt[a[x]];
	++num1[bl[a[x]]];
	if(cnt[a[x]]==1)	++num2[bl[a[x]]];
}
IL void remove(int x)
{
	--cnt[a[x]];
	--num1[bl[a[x]]];
	if(cnt[a[x]]==0)	--num2[bl[a[x]]];
}
int ans1[QN],ans2[QN];
IL void solve(int x)
{
	int ans1=0,ans2=0;
	int l=b[x].a,r=b[x].b;
	if(bl[l]==bl[r]){
		for(int i=l;i<=r;++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
	}
	else{
		for(int i=bl[l]+1;i<=bl[r]-1;++i){
			ans1+=num1[i];ans2+=num2[i];
		}
		for(int i=l;i<=rblk[bl[l]];++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
		for(int i=lblk[bl[r]];i<=r;++i){
			ans1+=cnt[i];ans2+=(cnt[i]>0);
		}
	}
	::ans1[b[x].id]=ans1;
	::ans2[b[x].id]=ans2;
}
IL void MAIN()
{
	int curl=1,curr=0; 
	for(int i=1;i<=qn;++i){
		while(curl<b[i].l){
			remove(curl);++curl;
		}
		while(curl>b[i].l){
			--curl;add(curl);
		}
		while(curr<b[i].r){
			++curr;add(curr);
		}
		while(curr>b[i].r){
			remove(curr);--curr;
		}
		solve(i);
	}
	for(int i=1;i<=qn;++i){
		printf("%d %d\n",ans1[i],ans2[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=io;
	}
	for(int i=1;i<=qn;++i){
		b[i].l=io;b[i].r=io;b[i].a=io;b[i].b=io;
		b[i].id=i;
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=(i-1)*blk+1;
		rblk[i]=i*blk;
	}
	rblk[nb]=n;
	
	sort(b+1,b+qn+1,cmp);
	MAIN();
	return 0;
}

luogu1903 [国家集训队]数颜色/维护队列
带修改莫队：多了一个时间轴。排序第一关键字是左端点所在块编号，第二关键字是右端点所在块编号，第三关键字是时间。左指针移动的复杂度为q·n，右指针的复杂度为n/m·n，时间轴的指针的复杂度为n/m·n/m·q，n和q同阶的时候，m取n^(2/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
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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL 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^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=133333+8,QN=133333+8,VAL=1000000+8;
const int blk=6000;
int n,qn,qn1,qn2;
int a[N],c[N];
int bl[N];
struct ques1{
	int l,r,id,cur;
}b1[QN];
struct ques2{
	int pos,a,b;
}b2[QN];
IL bool cmp(const ques1 &a,const ques1 &b)
{
	if(bl[a.l]!=bl[b.l])	return a.l<b.l;
	if(bl[a.r]!=bl[b.r])	return a.r<b.r;
	return a.cur<b.cur;
}
int curl=1,curr=0,cur=0;
int tot=0,cnt[VAL];
IL void add(int x)
{
	++cnt[x];
	if(cnt[x]==1)	++tot;
}
IL void remove(int x)
{
	--cnt[x];
	if(cnt[x]==0)	--tot;
} 
IL void change(int pos,int x)
{
	if(curl<=pos&&pos<=curr){
		remove(a[pos]);
		add(x);
	}
	a[pos]=x;
}
int ans[QN];
IL void MAIN()
{
	for(int i=1;i<=qn1;++i){
		while(cur<b1[i].cur){
			++cur;
			change(b2[cur].pos,b2[cur].b);
		}
		while(cur>b1[i].cur){
			change(b2[cur].pos,b2[cur].a);
			--cur;
		}
		while(curl<b1[i].l){
			remove(a[curl]);++curl;
		}
		while(curl>b1[i].l){
			--curl;add(a[curl]);
		}
		while(curr<b1[i].r){
			++curr;add(a[curr]);
		}	
		while(curr>b1[i].r){
			remove(a[curr]);--curr;
		}
		ans[b1[i].id]=tot;
	}
	for(int i=1;i<=qn1;++i){
		printf("%d\n",ans[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=c[i]=io;
		bl[i]=(i-1)/blk+1;
	}
	for(int i=1;i<=qn;++i){
		char ch;
		scanf("%c",&ch);
		if(ch=='Q'){
			++qn1;
			b1[qn1].l=io;b1[qn1].r=io;
			b1[qn1].id=qn1;b1[qn1].cur=qn2;
		}
		else{
			++qn2;
			b2[qn2].pos=io;
			b2[qn2].a=c[b2[qn2].pos];
			c[b2[qn2].pos]=b2[qn2].b=io;
		}
	}
	sort(b1+1,b1+qn1+1,cmp);
	MAIN();
	return 0;
}

atcoder1219 歴史の研究
回滚莫队：用来处理不适合添加或者删除的情况。对于处于同一块的左指针，每次移动之前将左指针放在下一个块的第一个位置，移动之后再把左指针放到下一个块的第一个位置。这样可以使得问题只有添加没有删除（或者删除变的可以处理）。复杂度同普通莫队。

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL 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^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=100000+8,QN=100000+8,NB=350;
const int blk=300;
int n,qn;
int tot,ori[N],a[N];
struct ques{
	int l,r,id;
}b[QN];
int nb,bl[N],lblk[NB],rblk[NB];
IL bool cmp(const ques &a,const ques &b)
{
	if(bl[a.l]!=bl[b.l])	return bl[a.l]<bl[b.l];
	return a.r<b.r;	
}
int cnt[N];
LL ans[QN];
IL void MAIN()
{
	int curl=0,curr=0;
	LL ans=0,tmp=0;
	for(int i=1;i<=qn;++i){
		int l=b[i].l,r=b[i].r;
		if(bl[l]!=bl[b[i-1].l]){
			curl=rblk[bl[l]]+1;
			curr=rblk[bl[l]];
			tmp=0;
			memset(cnt,0,sizeof(cnt));
		}
		if(bl[l]==bl[r]){
			ans=0;
			for(int i=l;i<=r;++i){
				++cnt[a[i]];
				ans=max(ans,1ll*cnt[a[i]]*ori[a[i]]);
			}
			for(int i=l;i<=r;++i){
				--cnt[a[i]];
			}
			::ans[b[i].id]=ans;
			continue;
		}
		while(curr<r){
			++curr;++cnt[a[curr]];
			tmp=max(tmp,1ll*cnt[a[curr]]*ori[a[curr]]);
		}
		ans=tmp;
		while(curl>l){
			--curl;++cnt[a[curl]];
			ans=max(ans,1ll*cnt[a[curl]]*ori[a[curl]]);
		}
		while(curl<rblk[bl[l]]+1){
			--cnt[a[curl]];++curl;
		}
		::ans[b[i].id]=ans;
	}
	for(int i=1;i<=qn;++i){
		printf("%lld\n",::ans[i]);
	}
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		ori[i]=a[i]=io;
	}
	sort(ori+1,ori+n+1);
	tot=unique(ori+1,ori+n+1)-ori-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
	}
	
	for(int i=1;i<=qn;++i){
		b[i].l=io;b[i].r=io;
		b[i].id=i;
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;	
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=(i-1)*blk+1;
		rblk[i]=i*blk;
	}
	rblk[nb]=n;
	
	sort(b+1,b+qn+1,cmp);
	MAIN();
	return 0;
}

区间众数
离线：回滚莫队 时间n·sqrt(q) 空间n
在线：分块 时间n·sqrt(q) 空间n

luogu5048 [Ynoi2019模拟赛]Yuno loves sqrt technology III
区间众数 众数的次数 在线
先离散化数据，将每个数据都放到对应的桶里(vector)，并记下排名。
再预处理一个f[i][j]表示第i个块到第j个块中的众数是多少，同时也可以记下众数是什么。
对于每一个[l,r]，ans开始是f[bl[l]+1][bl[r]-1]为中间块的众数。
对于左边的数字，在其对应的vector中找从他开始往后ans个数的位置是否<=r(首先要保证有后ans个数)，如果有则++ans
对于右边的数字，在其对应的vector中找从他开始往前ans个数的位置是否>=l(首先要保证有前ans个数)，如果有则++ans
复杂度：ans自增最多blk次，因为每次更新的数的位置要跨越[bl[l]+1][bl[r]-1]，这样就是两边区间的数的个数。预处理复杂度为n·n/m，每次查询复杂度为m，总复杂度n·n/m+q·m

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
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int U;
typedef unsigned long long LLU;
typedef pair<int,int> PII;
typedef long double LD;
IL LL read()
{
	LL 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^48);ch=getchar();}
	return x*f;
}
#define io read()
const int N=500000+8,NB=750;
const int blk=700;
int n,qn,nb;
int ori[N],tot,a[N];
int bl[N],lblk[N],rblk[N];
int f[NB][NB];
int pos[N];
vector<int> set_pos[N];
int cnt[N];
int l,r,lstans;
IL void MAIN()
{
	int ans=0;
	while(qn--){
		l=io^lstans;r=io^lstans;
		if(bl[l]+1<=bl[r]-1)	ans=f[bl[l]+1][bl[r]-1];
		else	ans=0;
		if(bl[l]==bl[r]){
			for(int i=l;i<=r;++i){
				while(pos[i]+ans<set_pos[a[i]].size()&&set_pos[a[i]][pos[i]+ans]<=r){
					++ans;
				}
			}
		} 
		else{
			for(int i=l;i<=rblk[bl[l]];++i){
				while(pos[i]+ans<set_pos[a[i]].size()&&set_pos[a[i]][pos[i]+ans]<=r){
					++ans;
				}
			}
			for(int i=lblk[bl[r]];i<=r;++i){
				while(pos[i]-ans>=0&&set_pos[a[i]][pos[i]-ans]>=l){
					++ans;
				}
			}
		}
		printf("%d\n",ans);
		lstans=ans; 
	}	
}
int main()
{
	n=io;qn=io;
	for(int i=1;i<=n;++i){
		a[i]=ori[i]=io;
	}
	sort(ori+1,ori+n+1);
	tot=unique(ori+1,ori+n+1)-ori-1;
	for(int i=1;i<=n;++i){
		a[i]=lower_bound(ori+1,ori+tot+1,a[i])-ori;
		pos[i]=set_pos[a[i]].size();
		set_pos[a[i]].pb(i);
	}
	
	for(int i=1;i<=n;++i){
		bl[i]=(i-1)/blk+1;
	}
	nb=bl[n];
	for(int i=1;i<=nb;++i){
		lblk[i]=blk*(i-1)+1;
		rblk[i]=blk*i;
	}
	rblk[nb]=n;
	
	for(int i=1;i<=n;i+=blk){
		memset(cnt,0,sizeof(cnt));
		int t=0;
		for(int j=i;j<=n;++j){
			++cnt[a[j]];
			if(cnt[a[j]]>t)	t=cnt[a[j]];
			if(rblk[bl[j]]==j){
				f[bl[i]][bl[j]]=t;
			}
		}
	}
	
	MAIN();
	return 0;
}