第七课倍增算法学习笔记
A静态区间最小值查询
题意
有给你一个数组，给你两个下标，问你区间最小值。
解法
我们可以设状态 $dp_{i,j}$ 表示 $i$ 位置往后 $2^j-1$ 个位置的最小值是多少。
而考虑到用二进制不能完全覆盖，假设要求出 $x$ 和 $y$ 之间的最小值，用二进制无法完全覆盖，则设 $k$ 为 $2^k < y - x + 1$ 满足要求的最大值，则区间最小值为 $min(dp_{x,k},dp_{y-(1<<k)+1,k})$，其实第二个就是在补充第一个为覆盖完整的区间。
而预处理出这样的一个 $dp$ 数组，我们可以将第二个下标为 $0$ 的先预处理，然后从第二个下标为 $1$ 的开始，而可以得出转移方程 $dp_{i,j}=min(dp_{i,j-1},dp_{i+(1<<(j-1)),j-1})$，因为是二进制，所以 $j-1$ 的这两段刚刚好平分 $i$ 到 $i+2^j$ 这段区间。
而得出 $k$，我们可以求出第 $i$ 个位置需要二的几次方才能够到（要小于）,可以利用递推思想，$f_i = f_{i>>1} + 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
| #include <bits/stdc++.h>
using namespace std;
const int inf = (int)1e9;
int n,m;
int a[100010];
int dp[27][100010];
int Log[100010];
void init()
{
for(int i=1;i<=n;i++) for(int j=1;j<=22;j++) dp[j][i]=inf;
for(int i=1;i<=n;i++) dp[0][i]=a[i];
for(int j=1;j<=25;j++)
{
int lim=n-(1<<j)+1;
for(int i=1;i<=lim;i++) dp[j][i]=min(dp[j-1][i],dp[j-1][i+(1<<(j-1))]);
}
Log[0]=-1;
for(int i=1;i<=n;i++) Log[i]=Log[(i>>1)]+1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init();
while(m--)
{
int x,y;
scanf("%d%d",&x,&y);
x++,y++;
int k=Log[(y-x+1)];
printf("%d\n",min(dp[k][x],dp[k][y-(1<<k)+1]));
}
}
|
B 众数查询
题意
给你一个序列和多次询问，每次给你两个数 $l$ 和 $r$。问你这段区间出现最多次数的数出现了多少次？
解法
根据这篇题解做出的题
首先我们可以预处理出这样的一个数组：
而 $l$ 和 $r$ 有可能刚还在这些块的中间，也有可能刚好在这些块的开头和结尾。
由于序列是单调不减的，所以 $l$ 和 $r$ 之间会有完整的块，这时候我们找到 $l$ ,$r$ 之间最左边的块的左端点和最右边的块的右端点，这样比较好维护。
而此时我们就可以用RMQ来做了，直接照抄模板：
1
2
3
4
5
6
7
8
9
10
11
| void RMQ()
{
Log[0]=-1;
for(int i=1;i<=idx;i++) Log[i]=Log[i>>1]+1;
for(int i=1;i<=idx;i++) dp[i][0]=cnt[i];
for(int j=1;j<22;j++)
{
int lim=(idx-(1<<j)+1);
for(int i=1;i<=lim;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
|
而 $l$，$r$ 之间完整的块就可以找到$l$ ,$r$ 之间最左边的块的左端点和最右边的块的右端点，然后输出 $max(dp_{l+1,k},dp_{r-2^k+1,k})$（$k$ 表示满足 $2^k<r-l+1$ 的最大值）。
我们可以用二分来找到这个边界位置所在的块（注意是块不是下标，上面转移方程的 $l$,$r$ 也是块的下标二分数组中的下标）。
然后由于 $l$,$r$ 二分之后会放弃掉一部分，舍弃部分可能对答案造成影响，所以我们要判断 $max(r-presum_R,presum_L-l+1)$ ,$presum$ 存的是每个块的末尾在数组中对应的下标，而 $r$ 表示输入的右端点，$l$ 同理，而 $R$,$L$ 表示二分后的左右端点（这个算的非常妙，最近的块的右端点直接一减就能得到答案）。
然后直接贴代码
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
| #include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp[N][22],a[N],last[N],cnt[N],presum[N];
int n,m;
int idx=0;int Log[N];
int findl(int l)
{
int L=1,R=idx;
int ans=0;
while(L<=R)
{
int mid=(L+R)/2;
if(presum[mid]<l) ans=mid,L=mid+1;
else R=mid-1;
}
return ans+1;
}
int findr(int l)
{
int L=1,R=idx;
int ans=0;
while(L<=R)
{
int mid=(L+R)/2;
if(presum[mid]<l) ans=mid,L=mid+1;
else R=mid-1;
}
return ans;
}
void RMQ()
{
Log[0]=-1;
for(int i=1;i<=idx;i++) Log[i]=Log[i>>1]+1;
for(int i=1;i<=idx;i++) dp[i][0]=cnt[i];
for(int j=1;j<22;j++)
{
int lim=(idx-(1<<j)+1);
for(int i=1;i<=lim;i++) dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=a[i-1]) cnt[++idx]=0;
cnt[idx]++;
}
for(int i=1;i<=idx;i++) presum[i]=presum[i-1]+cnt[i];
RMQ();
while(m--)
{
int l,r;
scanf("%d%d",&l,&r);
int R=r,L=l;
L=findl(l);
R=findr(r);
if(L==R)
{
printf("%d\n",max(presum[L]-l+1,r-presum[R]));
continue;
}
if(L>R)
{
printf("%d\n",r-l+1);
continue;
}
int k=Log[(R-L)];
printf("%d\n",max(max(dp[L+1][k],dp[R-(1<<k)+1][k]),max(r-presum[R],presum[L]-l+1)));
}
}
|
C 区间查询
好，这道题搞了两天半才搞懂，我是废物。
题意
给定 $n$ 个区间以及m个询问,每次询问给出 $a$，$b$。
询问 $a$，$b$ 之间最多可以选取多少不相交的区间。在端点处相交不算。
解法
这道题的状态表示有点玄学，虽然思路差不多，但吴校长和RF_RT都给出了不同的解释，反正我是下面这么理解的也不知道对不对，反正都过了就不管了。
我的理解是，$dp_{i,j}$ 表示从第 $i$ 个区间往后 $2^j$ 个区间的最小右端点。
非常需要注意的是，$i$ 表示区间的编号，或者说下标，这也是我跟上面两位神仙理解状态的不同之处，而往后 $2^j$ 个区间表示的就是往后各不相邻的 $2^j$ 个区间。
然后先初始化 $dp_{i,0}$ 的状态，这里可以使用一点贪心来去重无效区间，即：
1
2
3
4
5
| int nn=1;
for(int i=2;i<=n;i++)
{
if(seg[nn].l<seg[i].l) seg[++nn]=seg[i];
}
|
注意 $nn$ 不能从 $0$ 开始，因为区间的取值范围包括了 $0$。所以直接比较的话 $seg_{0}$ 的初始值为 $0$，可能会被循环卡掉（我最后就是错这里改完就过了所以这里十分值得注意QAQ）。
然后对于初始化当让就是：
1
2
3
4
5
6
| for(int i=1;i<=nn;i++)
{
f[i][0]=i+1;
while(f[i][0]<=nn && seg[f[i][0]].l<seg[i].r) f[i][0]++;
if(f[i][0]==nn+1) f[i][0]=-1;
}
|
这个 $while$ 循环就是找 $i$ 区间之后第一个不与当前区间相交的区间，当然之前也是状态理解错了所以一直看不懂。当状态理解对时再来看有种“山重水复疑无路，柳暗花明又一村”的感觉。
然后当匹配越界都无法满足的时候就直接 $-1$，因为状态是指第 $i$ 个区间之后，所以当前区间不在考虑范围内。
状态转移很妙，但理解起来不难：
1
2
3
4
5
6
7
| for(int j=0;j<31;j++)
{
for(int i=1;i<=nn;i++)
{
if(f[i][j]!=-1) f[i][j+1]=f[f[i][j]][j];
}
}
|
跟前两到板子题“拆成两段合并”有异曲同工之妙。
最后是答案的判断了。
我们可以用二分找到大于左端点且距离最近的区间（是过滤后的），作为左端点，用 $dp$ 数组算右端点，用了一个二进制十分巧妙地考虑了右端点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int x=-1,l=1,r=nn;
if(a>b) swap(a,b);
while(l<r)
{
int mid=(l+r)/2;
if(seg[mid].l<a) l=mid+1;
else r=mid,x=mid;
}
x=l;
if(seg[x].l<a || seg[x].r>b)
{
puts("0");
continue;
}
int ans=0;
for(int i=30;i>=0;i--)
{
if(f[x][i]!=-1 && seg[f[x][i]].r<=b)
{
ans+=(1<<i);
x=f[x][i];
}
}
|
然后这道题就做完了才怪。
注意，答案输出的时候要加一，因为 $dp$ 数组状态表示的是 $i$ 之后的区间，所以这个他没算进去。
然后就做完啦。
代码
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
| #include <bits/stdc++.h>
using namespace std;
int n,m;
int f[200010][32];
struct node
{
int l,r;
bool operator < (const node&cmp)
{
if(r==cmp.r) return l>cmp.l;
return r<cmp.r;
}
};
node seg[200010];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&seg[i].l,&seg[i].r);
sort(seg+1,seg+n+1);
int nn=1;
for(int i=2;i<=n;i++)
{
if(seg[nn].l<seg[i].l) seg[++nn]=seg[i];
}
memset(f,-1,sizeof f);
for(int i=1;i<=nn;i++)
{
f[i][0]=i+1;
while(f[i][0]<=nn && seg[f[i][0]].l<seg[i].r) f[i][0]++;
if(f[i][0]==nn+1) f[i][0]=-1;
}
for(int j=0;j<31;j++)
{
for(int i=1;i<=nn;i++)
{
if(f[i][j]!=-1) f[i][j+1]=f[f[i][j]][j];
}
}
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
int x=-1,l=1,r=nn;
if(a>b) swap(a,b);
while(l<r)
{
int mid=(l+r)/2;
if(seg[mid].l<a) l=mid+1;
else r=mid,x=mid;
}
x=l;
if(seg[x].l<a || seg[x].r>b)
{
puts("0");
continue;
}
int ans=0;
for(int i=30;i>=0;i--)
{
if(f[x][i]!=-1 && seg[f[x][i]].r<=b)
{
ans+=(1<<i);
x=f[x][i];
}
}
printf("%d\n",ans+1);
}
}
|
D 区间覆盖
题意
给定 $n$ 个区间以及m个询问,每次询问给出 $a$，$b$。
询问最少要选取多少个区间才能完全覆盖 $[a, b]$ 区间。
无法覆盖输出 $-1$。
解法
发现 $x$，$y$ 范围不大，所以我们可以先预处理出每个左端点用一条线段最远能到达哪个右端点。
然后直接在这整一条数轴上做一个 $st$ 表。$dp_{i,j}$ 表示从 $i$ 这个点（表示数轴上的某一个点）经过 $2^j$ 条线段能到达的最远距离。
最后是访问，我们可以做一个类似 $C$ 题的区间分解，把 $l$，$r$ 范围内分解成一个个由二进制组成的小块。
最后如果发现 $x$ 够不着 $r$ 就输出 $-1$，否则输出答案。
值得一提的是，我们发现区间可能会出现不连通的现象，但是如果我们仔细想会发现如果出现不连通，上面的预处理会出现他的值比 $i$ 本身还小的情况，所以不需要管。
代码
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>
using namespace std;
const int N=600005;
int n,m,l,r,ma,a[N],f[N][22];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&l,&r);
a[l]=max(a[l],r);
ma=max(ma,r);
}
for(int i=1;i<=ma;i++)a[i]=max(a[i],a[i-1]);
for(int i=0;i<=ma;i++)f[i][0]=a[i];
for(int i=1;i<=20;i++)for(int j=0;j<=ma;j++)f[j][i]=f[f[j][i-1]][i-1];
while(m--)
{
scanf("%d%d",&l,&r);
int ans=0;
for(int i=20;i>=0;i--)
{
if(f[l][i]<r)
{
ans+=1<<i;
l=f[l][i];
}
}
if(a[l]>=r)printf("%d\n",ans+1);
else puts("-1");
}
}
|
E 子矩阵查询
题意
给定一个 $N \times N$ 的矩阵，和一个整数 $B$。
有 $K$ 次询问,每次询问给出一对 $x$，$y$。
求以 $(x，y)$ 为左上角的 $B \times B$ 的子矩阵中的最大差值是多少。
解法
我们发现 $n$，$b$ 非常小，$k$ 又非常大，所以我们应把重心移到预处理上，然后 $O(1)$ 查询。
首先我们给矩阵的每一行都预处理一个 $st$ 表分别为最大值和最小值，这里的预处理直接套A题板子题的模板就行了。
然后由于 $B$ 已经给定，所以我们可以预处理一个数组 $kk_{x,y}$ 表示从点 $(x，y)$ 开始的一个 $B \times B$ 的矩阵最大值是多少（当然还得预处理最小值），预处理方法就是从 $x$ 开始到 $x+b-1$ 用之前预处理的那个 $st$ 表一行一行暴力算，因为 $n$ 和 $b$ 都不是很大，所以不会超时。
最后直接 $O(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
68
69
| #include <bits/stdc++.h>
using namespace std;
int n,b,k;
int a[251][251];
int f1[251][251][10],f2[251][251][10];
int kk[251][251][2];
int main()
{
scanf("%d%d%d",&n,&b,&k);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<10;k++)
{
f1[i][j][k]=0x3f3f3f3f;
f2[i][j][k]=0;
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) f1[i][j][0]=f2[i][j][0]=a[i][j];
}
for(int i=1;i<=n;i++)
{
for(int k=1;k<=8;k++)
{
int lim=(n-(1<<k))+1;
for(int j=1;j<=lim;j++)
{
f1[i][j][k]=min(f1[i][j][k-1],f1[i][j+(1<<(k-1))][k-1]);
f2[i][j][k]=max(f2[i][j][k-1],f2[i][j+(1<<(k-1))][k-1]);
}
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++) kk[i][j][0]=0x3f3f3f3f;
}
int e=0;
for(int i=10;i>=0;i--)
{
if((1<<i)<=b)
{
e=i;
break;
}
}
for(int i=1;i+b-1<=n;i++)
{
for(int j=1;j+b-1<=n;j++)
{
for(int k=i;k<=i+b-1;k++)
{
kk[i][j][0]=min(kk[i][j][0],min(f1[k][j][e],f1[k][j+b-1-(1<<e)+1][e]));
kk[i][j][1]=max(kk[i][j][1],max(f2[k][j][e],f2[k][j+b-1-(1<<e)+1][e]));
}
}
}
while(k--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",kk[x][y][1]-kk[x][y][0]);
}
}
|
