「算法笔记」分块算法

分块算法,和莫队有着异曲同工之妙,是一种优雅的暴力。

概述

分块算法,顾名思义是把一个长度为 $n$ 的序列分成 $m$ 块,每块的大小均为 $\frac{n}{m}$。我们维护块内信息,使得块内信息的查询是 $O(1)$ 的,而总的询问又可以看做是若干个块的询问的总和。

为了方便描述,我们定义:

  • 完整块:区间操作时,完整包含于区间的块。
  • 不完整的块:区间操作时,只有部分包含于区间的块,即左右端点所在的两个块。
  • 零散元素:不完整的块内的元素。

我们发现,对于一个询问 $[l,r]$,我们可以进行如下处理:

  • 拆成若干个完整块,其中每个完整快内的信息可以 $O(1)$ 更新。其中完整块的数量为 $O(\frac{n}{m})$。
  • 剩下两个不完整的块,对于这两个块内的信息暴力更新。其中不完整的块的大小为 $O(m)$。

综上所述,分块算法单次操作的时间复杂度为 $O(\frac{n}{m}+m)$。根据均值不等式,我们可以发现 $m=\sqrt n$ 时复杂度最优。


如何分块

我们定义如下变量:

$len$ $num$ $bl[i]$ $l[i]$ $r[i]$
块的大小 块的数量 第 $i$ 个元素所属的块 第 $i$ 个块的左端点 第 $i$ 个块的右端点

那么我们可以用如下代码建立分块:

其中特别需要注意 r[num]=n 意味着第 $num$ 个块(最后一个块)的右端点一定是 $n$!

1
2
3
4
5
6
void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}

接下来我们就用 $9​$ 个来自 LOJ 的例题(可能稍有修改)来简单讲解一下分块的思想。


例题 1

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,单点求值。

Solution

我们用 $tag[i]$ 记录第 $i$ 个块内每个元素都加的值。

对于修改操作 $[x,y]$ 有两种情况:

  • 其中 $x$ 和 $y$ 在同一个块内,那么直接暴力修改 $a[i]$ 的值即可。
  • 其中 $x$ 和 $y$ 不在同一个块内,那么先修改整块 $(bl[x],bl[y])$ 的 $tag$ 值,然后再对 $x$ 和 $y$ 所在的块内的零散元素暴力修改 $a[i]$ 的值。

对于查询操作 $x$,直接输出 $a[x]+tag[bl[x]]$ 的值。

时间复杂度:$O(m\sqrt n)$

Code

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
#include <cstdio>
#include <cmath>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],tag[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) a[i]+=v;
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) tag[i]+=v;
for(int i=x;i<=r[bl[x]];++i) a[i]+=v;
for(int i=l[bl[y]];i<=y;++i) a[i]+=v;
}
}
int query(int x) {
return a[x]+tag[bl[x]];
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt;
scanf("%d",&opt);
if(!opt) {
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
modify(x,y,v);
} else {
int x;
scanf("%d",&x);
printf("%d\n",query(x));
}
}
return 0;
}

例题 2

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间查询小于 $v$ 的元素个数。

Solution

我们首先考虑没有修改操作怎么做:

  • 对于零散元素,我们直接暴力查找。
  • 对于整块,我们可以先排序然后直接二分查找。

如果有了修改操作,那么意味着我们每次修改后需要重新排序,还是分成两部分考察:

  • 对于零散元素,我们暴力修改后对不完整块直接重新排序。时间复杂度为 $O(\sqrt n\log n)$。
  • 对于整块,我们发现修改不影响元素之间的相对顺序,所以不需要排序。查询时需要用 $v-tag[i]$ 的值二分查找。时间复杂度为 $O(\sqrt n)$。

时间复杂度:$O(m\sqrt n\log n)$(其中可以用均值不等式计算出更优的复杂度 QAQ)

Code

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],tag[M];
std::vector<int> ve[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) {
bl[i]=(i-1)/len+1;
ve[bl[i]].push_back(a[i]);
}
for(int i=1;i<=num;++i) {
l[i]=(i-1)*len+1,r[i]=i*len;
std::sort(ve[i].begin(),ve[i].end());
}
r[num]=n;
}
void reset(int x) {
ve[x].clear();
for(int i=l[x];i<=r[x];++i) ve[x].push_back(a[i]);
std::sort(ve[x].begin(),ve[x].end());
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) a[i]+=v;
reset(bl[x]);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) tag[i]+=v;
for(int i=x;i<=r[bl[x]];++i) a[i]+=v;
for(int i=l[bl[y]];i<=y;++i) a[i]+=v;
reset(bl[x]),reset(bl[y]);
}
}
int query(int x,int y,int v) {
int ans=0;
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) if(a[i]+tag[bl[i]]<v) ++ans;
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) {
ans+=std::lower_bound(ve[i].begin(),ve[i].end(),v-tag[i])-ve[i].begin();
}
for(int i=x;i<=r[bl[x]];++i) if(a[i]+tag[bl[i]]<v) ++ans;
for(int i=l[bl[y]];i<=y;++i) if(a[i]+tag[bl[i]]<v) ++ans;
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x,y,v;
scanf("%d%d%d%d",&opt,&x,&y,&v);
if(!opt) {
modify(x,y,v);
} else {
printf("%d\n",query(x,y,v));
}
}
return 0;
}

例题 3

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间查询 $v$ 的前驱。

Solution

我们有一个很直观的想法:直接沿用例题 2 的思路,只要修改一下二分即可。

但是这题有一个更简单的方法,直接用 $\text{set}$ 维护块内信息。这样甚至可以支持插入和删除操作,更加方便。但是 $\text{set}$ 常数巨大,所以此题不建议使用 $\text{set}​$ 来维护。

时间复杂度:$O(m\sqrt n\log n)$

Code

直接二分查找

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],tag[M];
std::vector<int> ve[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) {
bl[i]=(i-1)/len+1;
ve[bl[i]].push_back(a[i]);
}
for(int i=1;i<=num;++i) {
l[i]=(i-1)*len+1,r[i]=i*len;
std::sort(ve[i].begin(),ve[i].end());
}
r[num]=n;
}
void reset(int x) {
ve[x].clear();
for(int i=l[x];i<=r[x];++i) ve[x].push_back(a[i]);
std::sort(ve[x].begin(),ve[x].end());
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) a[i]+=v;
reset(bl[x]);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) tag[i]+=v;
for(int i=x;i<=r[bl[x]];++i) a[i]+=v;
for(int i=l[bl[y]];i<=y;++i) a[i]+=v;
reset(bl[x]),reset(bl[y]);
}
}
int query(int x,int y,int v) {
int ans=-1;
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) {
std::vector<int>::iterator it=std::lower_bound(ve[i].begin(),ve[i].end(),v-tag[i]);
if(it!=ve[i].begin()) ans=std::max(ans,*(--it)+tag[i]);
}
for(int i=x;i<=r[bl[x]];++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
for(int i=l[bl[y]];i<=y;++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x,y,v;
scanf("%d%d%d%d",&opt,&x,&y,&v);
if(!opt) {
modify(x,y,v);
} else {
printf("%d\n",query(x,y,v));
}
}
return 0;
}

使用 $\text{set}$ 维护

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
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <set>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],tag[M];
std::set<int> s[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1,s[bl[i]].insert(a[i]);
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void update(int x,int v) {
s[bl[x]].erase(a[x]),s[bl[x]].insert(a[x]+=v);
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) update(i,v);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) tag[i]+=v;
for(int i=x;i<=r[bl[x]];++i) update(i,v);
for(int i=l[bl[y]];i<=y;++i) update(i,v);
}
}
int query(int x,int y,int v) {
int ans=-1;
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) {
std::set<int>::iterator it=s[i].lower_bound(v-tag[i]);
if(it!=s[i].begin()) ans=std::max(ans,*(--it)+tag[i]);
}
for(int i=x;i<=r[bl[x]];++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
for(int i=l[bl[y]];i<=y;++i) {
int val=a[i]+tag[bl[i]];
if(val<v) ans=std::max(ans,val);
}
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x,y,v;
scanf("%d%d%d%d",&opt,&x,&y,&v);
if(!opt) {
modify(x,y,v);
} else {
printf("%d\n",query(x,y,v));
}
}
return 0;
}

例题 4

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间加法,区间求和。答案对 $10^9+7$ 取模。

Solution

这题还是和例题 1 一样的思路,只不过需要多维护一个区间和:我们定义 $sum[i]$ 表示第 $i$ 个块的总和(不包括 $tag[i]$ 的值,也就是说这两者是独立的)。

我们先分析修改操作,对于两种情况分类讨论:

  • 对于零散元素,我们暴力修改 $a[i]$ 和 $sum[bl[i]]$ 的值。
  • 对于整块,只需要修改 $tag[i]$ 的值即可,而不需要修改 $sum[i]$ 的值。

我们再分析查询操作,对于两种情况分类讨论:

  • 对于零散元素,我们用 $a[i]+tag[bl[i]]$ 来更新答案。

  • 对于整块,经过简单的思考就可以发现答案就是 $sum[i]+tag[i]\times len$ 的总和。

    为什么可以直接用 $len$ 的值?因为我们在统计时,只使用 $(bl[x],bl[y])$ 这个闭区间内的整块,不涉及最后一个块,所以每个块的大小必为 $len$。

时间复杂度:$O(m\sqrt n)$

Code

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
#include <cstdio>
#include <cmath>

const int mod=1e9+7;
const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],tag[M],sum[M];

void upd(int &x,int y) {
(x+=y)>=mod&&(x-=mod);
}
void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1,upd(sum[bl[i]],a[i]);
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) a[i]+=v;
upd(sum[bl[x]],1LL*(y-x+1)*v%mod);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) upd(tag[i],v);
for(int i=x;i<=r[bl[x]];++i) upd(a[i],v);
upd(sum[bl[x]],1LL*(r[bl[x]]-x+1)*v%mod);
for(int i=l[bl[y]];i<=y;++i) upd(a[i],v);
upd(sum[bl[y]],1LL*(y-l[bl[y]]+1)*v%mod);
}
}
int query(int x,int y) {
int ans=0;
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) upd(ans,a[i]);
upd(ans,1LL*(y-x+1)*tag[bl[x]]%mod);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) upd(ans,sum[i]),upd(ans,1LL*tag[i]*len%mod);
for(int i=x;i<=r[bl[x]];++i) upd(ans,a[i]);
upd(ans,1LL*(r[bl[x]]-x+1)*tag[bl[x]]%mod);
for(int i=l[bl[y]];i<=y;++i) upd(ans,a[i]);
upd(ans,1LL*(y-l[bl[y]]+1)*tag[bl[y]]%mod);
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(!opt) {
int v;
scanf("%d",&v);
modify(x,y,v);
} else {
printf("%d\n",query(x,y));
}
}
return 0;
}

例题 5

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间开方,区间求和。

Solution

由于有区间开方操作,没法直接更新区间和,问题貌似比较棘手。

但是我们可以分析一下开方的性质:一个 $10^9$ 的数字不断进行开方,其值大约为:$10^9,31622,177,13,3,1,1,1,\cdots$

那么意味着,每个数最多被开方大约 $5$ 次,这样我们可以记录每个块中是否有 $>1$ 的元素。如果没有则不需要对这个块内元素开方操作。

有了这个性质,直接暴力操作即可。

时间复杂度:$O(m\sqrt n)$

Code

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 <cstdio>
#include <cmath>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],sum[M];
bool flg[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1,sum[bl[i]]+=a[i];
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void solve(int x) {
if(flg[x]) return;
sum[x]=0,flg[x]=1;
for(int i=l[x];i<=r[x];++i) sum[x]+=(a[i]=sqrt(a[i])),flg[x]&=(a[i]<=1);
}
void modify(int x,int y) {
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) sum[bl[x]]-=a[i],sum[bl[x]]+=(a[i]=sqrt(a[i]));
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) solve(i);
for(int i=x;i<=r[bl[x]];++i) sum[bl[x]]-=a[i],sum[bl[x]]+=(a[i]=sqrt(a[i]));
for(int i=l[bl[y]];i<=y;++i) sum[bl[y]]-=a[i],sum[bl[y]]+=(a[i]=sqrt(a[i]));
}
}
int query(int x,int y) {
int ans=0;
if(bl[x]==bl[y]) {
for(int i=x;i<=y;++i) ans+=a[i];
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) ans+=sum[i];
for(int i=x;i<=r[bl[x]];++i) ans+=a[i];
for(int i=l[bl[y]];i<=y;++i) ans+=a[i];
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x,y;
scanf("%d%d%d",&opt,&x,&y);
if(!opt) {
modify(x,y);
} else {
printf("%d\n",query(x,y));
}
}
return 0;
}

例题 6

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持单点插入,单点求值。

Solution

首先考虑数据随机的情况,那么每个块内插入的操作是均摊的。我们只需要用 $\text{vector}$ 维护每个块,暴力插入查询即可,时间复杂度依旧为 $O(m\sqrt n)$。

我们发现,在极限数据下,某个块内可能会被插入至多 $O(m)$ 次,这样单次操作的复杂度就变成了 $O(m)$,显然是不能接受的。

我们发现,当一个块的大小过大时就会影响整体的复杂度。那么我们在块过大时进行重构分块,我们定义一个阈值 $k$,当某个块的大小超过 $k\times len$ 时,我们对整个序列进行重构。一般而言,这个阈值 $k$ 在 $20$ 左右复杂度较优。

当然还有一个方法:每进行 $\sqrt n$ 次插入操作后就进行重构。每次重构的复杂度为 $O(n+m)$,那么总体的复杂度还是 $O(m\sqrt n)$(默认 $n$ 和 $m$ 同阶)。

时间复杂度:$O(m\sqrt n)$

Code

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 <cstdio>
#include <cmath>
#include <vector>

const int N=1e5+5,M=500;
int n,m,len,num,a[N],st[N<<1];
std::vector<int> ve[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) ve[(i-1)/len+1].push_back(a[i]);
}
void rebuild() {
int top=0;
for(int i=1;i<=num;++i) {
for(int j=0;j<(int)ve[i].size();++j) st[++top]=ve[i][j];
ve[i].clear();
}
len=sqrt(top),num=(top-1)/len+1;
for(int i=1;i<=top;++i) ve[(i-1)/len+1].push_back(st[i]);
}
std::pair<int,int> get(int k) {
int x=1;
while(k>(int)ve[x].size()) k-=ve[x++].size();
return std::make_pair(x,k-1);
}
void insert(int x,int v) {
std::pair<int,int> r=get(x);
int i=r.first;
ve[i].insert(ve[i].begin()+r.second,v);
if((int)ve[i].size()>20*len) rebuild();
}
int query(int x) {
std::pair<int,int> r=get(x);
return ve[r.first][r.second];
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt,x;
scanf("%d%d",&opt,&x);
if(!opt) {
int v;
scanf("%d",&v);
insert(x,v);
} else {
printf("%d\n",query(x));
}
}
return 0;
}

例题 7

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间乘法,区间加法,单点求值。答案对 $10007$ 取模。

Solution

我们发现修改操作和「Luogu 3373」【模板】线段树 2 的套路非常相似。

首先我们强制乘法比加法优先。也就是说,块内维护两个标记 $add[i]$ 和 $mul[i]$ 分别表示整个块内加、乘的值。一个元素 $a[i]$ 实际表示的值为 $a[i]\times mul[bl[i]]+add[bl[i]]$。

  • 块内乘法 $v$:假如两个标记的值为 $A$ 和 $M$,那么标记变成 $A\times v$ 和 $M\times v$。
  • 块内加法 $v$:假如两个标记的值为 $A$ 和 $M$,那么标记变成 $A+v$ 和 $M$。

对于零散元素,我们无法直接修改,所以直接暴力将所在块内的标记转移到元素上,然后将标记清空($add[i]=0,mul[i]=1$),直接对零散元素本身修改即可。

Code

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
#include <cstdio>
#include <cmath>

const int mod=10007;
const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],add[M],mul[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len,mul[i]=1;
r[num]=n;
}
void upd(int &x,int y) {
(x+=y)>=mod&&(x-=mod);
}
void reset(int x) {
for(int i=l[x];i<=r[x];++i) a[i]=(a[i]*mul[x]+add[x])%mod;
add[x]=0,mul[x]=1;
}
void modifyAdd(int x,int y,int v) {
if(bl[x]==bl[y]) {
reset(bl[x]);
for(int i=x;i<=y;++i) upd(a[i],v);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) upd(add[i],v);
reset(bl[x]),reset(bl[y]);
for(int i=x;i<=r[bl[x]];++i) upd(a[i],v);
for(int i=l[bl[y]];i<=y;++i) upd(a[i],v);
}
}
void modifyMul(int x,int y,int v) {
if(bl[x]==bl[y]) {
reset(bl[x]);
for(int i=x;i<=y;++i) (a[i]*=v)%=mod;
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) (add[i]*=v)%=mod,(mul[i]*=v)%=mod;
reset(bl[x]),reset(bl[y]);
for(int i=x;i<=r[bl[x]];++i) (a[i]*=v)%=mod;
for(int i=l[bl[y]];i<=y;++i) (a[i]*=v)%=mod;
}
}
int query(int x) {
return (a[x]*mul[bl[x]]+add[bl[x]])%mod;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int opt;
scanf("%d",&opt);
if(!opt) {
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
modifyAdd(x,y,v%mod);
} else if(opt==1) {
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
modifyMul(x,y,v%mod);
} else {
int x;
scanf("%d",&x);
printf("%d\n",query(x));
}
}
return 0;
}

例题 8

给定一个长度为 $n$ 的序列和 $m$ 个操作。支持区间查询等于 $v$ 的元素个数并覆盖为 $v$。

Solution

我们先考虑一个暴力的做法,对于修改操作:

  • 对于零散元素,我们暴力修改。注意单点修改前需要下放标记
  • 对于整块,我们对这个块打上标记,表示整个块内的元素相同,均为 $v$。

然后考虑查询操作:

  • 对于零散元素,我们下放标记后暴力查询。
  • 对于整块,如果这个块内有标记且标记的值为 $v$,那么对答案有 $len$ 的贡献。如果没有标记,那么我们对 $[l[i],r[i]]$ 区间内的元素暴力查询

这个做法看上去单次查询的复杂度为 $O(n)$,但是我们这样分析:

假设初始序列都是同一个值,那么单次查询的复杂度为 $O(\sqrt n)$。如果这是进行一个区间操作,它最多破环首位 $2$ 个块的标记,所以只能使得后面的询问至多增加 $2$ 个块的暴力时间,所以均摊的单次复杂度为 $O(\sqrt n)$。

换句话说,要让一次操作耗费 $O(n)$ 的时间,要先花费 $O(\sqrt n)$ 个操作对数列进行修改!综上所述,总体时间复杂度为 $O(m\sqrt n)$。

时间复杂度:$O(m\sqrt n)$

Code

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
#include <cstdio>
#include <cmath>

const int N=1e5+5,M=320;
int n,m,len,num,a[N],bl[N],l[M],r[M],cov[M];
bool tag[M];

void build() {
len=sqrt(n),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void reset(int x) {
if(!tag[x]) return;
for(int i=l[x];i<=r[x];++i) a[i]=cov[x];
tag[x]=0;
}
void modify(int x,int y,int v) {
if(bl[x]==bl[y]) {
reset(bl[x]);
for(int i=x;i<=y;++i) a[i]=v;
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) tag[i]=1,cov[i]=v;
reset(bl[x]),reset(bl[y]);
for(int i=x;i<=r[bl[x]];++i) a[i]=v;
for(int i=l[bl[y]];i<=y;++i) a[i]=v;
}
}
int query(int x,int y,int v) {
int ans=0;
if(bl[x]==bl[y]) {
reset(bl[x]);
for(int i=x;i<=y;++i) ans+=(a[i]==v);
} else {
for(int i=bl[x]+1;i<=bl[y]-1;++i) {
if(tag[i]) {
ans+=(cov[i]==v?len:0);
} else {
for(int j=l[i];j<=r[i];++j) ans+=(a[j]==v);
}
}
reset(bl[x]),reset(bl[y]);
for(int i=x;i<=r[bl[x]];++i) ans+=(a[i]==v);
for(int i=l[bl[y]];i<=y;++i) ans+=(a[i]==v);
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build();
while(m--) {
int x,y,v;
scanf("%d%d%d",&x,&y,&v);
printf("%d\n",query(x,y,v));
modify(x,y,v);
}
return 0;
}

例题 9

给定一个长度为 $n$ 的序列和 $m​$ 个操作。支持区间查询最小众数。

Solution

以下解法中,我们为了方便表述,定义 $\text{mode}(i)$ 表示第 $i$ 个整块的众数。

解法 1(无修改)

我们首先可以发现一个性质:对于询问 $[x,y]$,答案 $\in\text{mode}(i\sim j)\cup\text{零散元素}$(其中 $\text{mode}(i\sim j$) 表示 $[x,y]$ 内的所有整块的众数)。令 $l,r$ 分别在第 $a,b$ 块,那么 $[l,r]$ 可以拆成:

  • 从 $l$ 到第 $a$ 块的最后一个元素。
  • 从第 $a+1$ 块到第 $b-1​$ 块。
  • 从第 $b$ 块的起始一个元素到 $r$。

根据这个性质,我们只需要至多比较 $2\sqrt n+1​$ 即 $O(\sqrt n)​$ 个数的出现次数即可。

那么我们可以 $O(n\sqrt n)$ 预处理 $f[i][j]$ 表示第 $i$ 个整块到第 $j$ 个整块的众数。然后对于每个种值开一个 $\text{vector}$ 记录值 $i$ 出现的位置。

接下来考虑询问 $[x,y]$ 怎么分解处理:

  • 对于零散元素,我们暴力查找每个元素在 $[x,y]​$ 内的出现次数,这个过程可以通过在记录 $a[i]​$ 出现位置的 $ve[a[i]]​$ 内二分查找实现。
  • 对于整块,众数为 $f[bl[x]+1][bl[y]-1]$,出现次数同理可以二分得到。

我们只需要在这 $O(\sqrt n)$ 个数内找到出现次数最多的数即可。

注意,为了方便计算需要事先对数据离散化

时间复杂度:$O(m\sqrt n\log n)$(可以通过均值不等式计算出块的大小为 $\sqrt{\frac{n}{\log n}}$ 以获得更优的复杂度通过本题)

期望得分:$80\sim100​$

解法 2(无修改)

我们考虑在解法 1 的基础上进行修改。首先 $\sqrt n$ 这个系数是肯定没法去掉了,考虑如何仍然在 $\sqrt n$ 分块下去掉 $\log n$ 这个系数。这意味着我们要在 $O(1)$ 的时间内回答询问。

不妨设 $F[i][x]$ 表示 $[0,i]$ 之间有多少个 $x$。那么 $[l,r]$ 之间的 $x$ 的数量就是 $F[r][x]-F[l-1][x]$,所以可以省去一个二分的 $\log n$。

预处理时,我们只需要对序列扫一遍即可,复杂度为 $O(n)​$。

时间复杂度:$O(m\sqrt n)$

期望得分:$100$

解法 3(带修改)

貌似可以 $\sqrt[3] n$ 分块?推荐阅读 区间众数解题报告 - 陈立杰 改日填坑

Code

解法 1

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
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>

const int N=1e5+5,M=1300;
int n,m,len,num,a[N],val[N],bl[N],l[M],r[M],cnt[N],f[M][M];
std::vector<int> p[N];

void build() {
for(int i=1;i<=n;++i) val[i]=a[i];
std::sort(val+1,val+n+1);
int sz=std::unique(val+1,val+n+1)-(val+1);
for(int i=1;i<=n;++i) {
a[i]=std::lower_bound(val+1,val+sz+1,a[i])-val;
p[a[i]].push_back(i);
}
len=sqrt(n/log2(n)),num=(n-1)/len+1;
for(int i=1;i<=n;++i) bl[i]=(i-1)/len+1;
for(int i=1;i<=num;++i) l[i]=(i-1)*len+1,r[i]=i*len;
r[num]=n;
}
void init() {
for(int i=1;i<=num;++i) {
memset(cnt,0,sizeof(cnt));
int ans=0,mx=0;
for(int j=i;j<=num;++j) {
for(int k=l[j];k<=r[j];++k) {
++cnt[a[k]];
if(cnt[a[k]]>mx||(cnt[a[k]]==mx&&a[k]<ans)) ans=a[k],mx=cnt[a[k]];
}
f[i][j]=ans;
}
}
}
int sum(int l,int r,int v) {
return std::upper_bound(p[v].begin(),p[v].end(),r)-std::lower_bound(p[v].begin(),p[v].end(),l);
}
void solve(int x,int y,int l,int r,int &ans,int &mx) {
for(int i=x;i<=y;++i) {
int now=sum(l,r,a[i]);
if(now>mx||(now==mx&&a[i]<ans)) ans=a[i],mx=now;
}
}
int query(int x,int y) {
int ans=0,mx=0;
if(bl[x]+1>=bl[y]) {
solve(x,y,x,y,ans,mx);
} else {
ans=f[bl[x]+1][bl[y]-1],mx=sum(x,y,ans);
solve(x,r[bl[x]],x,y,ans,mx);
solve(l[bl[y]],y,x,y,ans,mx);
}
return ans;
}
int main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
build(),init();
while(m--) {
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",val[query(x,y)]);
}
return 0;
}

解法 2

1
// 改日填坑

解法 3

1
// 改日填坑

习题

  • Ynoi 吼啊!改日填坑
0%