模版 | 倍增区间最值
初步接入：Balanced Lineup G（原题链接）
题意：
给出长度为n的静态数组和q次询问，接下n行为数组a的值，q行每次给你两个数a和b，求[a,b]区间内的最大值。
做题思路：
本题是倍增区间最值的模版题，依旧先讲倍增区间的使用条件：只能使用于数组查询可以重复贡献的数组。即当查询数组时出现重叠，但依旧满足题意的数组，如下图所示，选中的两个区间中出现了重叠的数组，但此时总区间长度中，最大的值依旧是2
所以本题是可以使用区间最值求解本题的，接下来是代码实现，首先是题目数据预处理，为了方便计算结果，我们需要先预处理数据，方便在询问时，直接得出需要的结果。
首先记录每个值会是2的几次幂，以便接下来的倍增预处理。
mylog2[0]=-1;
for (int i=1;i<=N;i++)mylog2[i]=mylog2[i>>1]+1;
图文演示：
倍增的预处理
for (int i=1;i<=n;i++)
{
//每个点长度为1时，最大/小值为自身
dp_max[i][0]=a[i];
dp_min[i][0]=a[i];
}
//直接拿取n的Log2的值
int m=mylog2[n];
for (int k=1;k<=m;k++)
{
//每次比较数组以s为起点，加上k的距离的最大/小值
for (int s=1;s+(1<<k)<=n+1;s++)
{
dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
}
}
图文演示：
在处理完数据后，之后每次输出只需查找每段分裂后区间的最大/小值即可。这里就是为什么必须要满足上面那个条件的原因，如果在重复段落会影响答案，代表不能使用该算法，如有计算两段区间内的值，区间[1,5]的和是5，[2,6]的和也是5,此时[1,6]的和为6，但如果使用概算法，重叠部分的值会进一步叠加导致答案变为10。
int query(int l,int r){
//区间长度
int k=mylog2[r-l+1];
//将区间截取两段，每次截取小于长度的2^k值
int newl=r-(1<<k)+1;
//比较两段的最大/小值
int x=max(dp_max[l][k],dp_max[newl][k]);
int y=min(dp_min[l][k],dp_min[newl][k]);
return x-y;
}
最后附上ac代码：
using namespace std;
const int N=1e6+10;
int n,q;
int a[N];
//记录每个点以2^k次为长度时，区间内的最大/最小值
//25因为2^25即可满足本题所有的点
int dp_max[N][25],dp_min[N][25];
//预先打出1-N中每个点log2的表节省时间
int mylog2[N];
void init(){
//log2不存在值为0的情况，避免报错
mylog2[0]=-1;
for (int i=1;i<=N;i++)mylog2[i]=mylog2[i>>1]+1;
for (int i=1;i<=n;i++)
{
//每个点长度为1时，最大/小值为自身
dp_max[i][0]=a[i];
dp_min[i][0]=a[i];
}
//直接拿取n的Log2的值
int m=mylog2[n];
for (int k=1;k<=m;k++)
{
//每次比较数组以s为起点，加上k的距离的最大/小值
for (int s=1;s+(1<<k)<=n+1;s++)
{
dp_max[s][k]=max(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
dp_min[s][k]=min(dp_min[s][k-1],dp_min[s+(1<<(k-1))][k-1]);
}
}
}
//计算区间最大差值
int query(int l,int r){
//区间长度
int k=mylog2[r-l+1];
//将区间截取两段，每次截取小于长度的2^k值
int newl=r-(1<<k)+1;
//比较两段的最大/小值
int x=max(dp_max[l][k],dp_max[newl][k]);
int y=min(dp_min[l][k],dp_min[newl][k]);
return x-y;
}
int main() {
cin >>n>>q;
for (int i=1;i<=n;i++)cin >>a[i];
init();
for (int i=1;i<=q;i++)
{
int l,r;
cin >>l>>r;
cout <<query(l,r)<<"\n";
}
return 0;
}
扩展应用： gcd区间（原题链接）
题意：
给你n个数组和m次查询，问数组区间内的最大公因数。
做题思路：
本题即是上题代码的应用，判断你是否理解倍增区间重叠贡献的含义。最大公因数为什么可以应用于本题，答：因为公因数是单独计算的，不管中间的值重复几次，他存在的最大公因数都不会变。
直接上代码：
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,q;
int a[N];
//25因为2^25即可满足本题所有的点
int dp_max[N][25];
//预先打出1-N中每个点log2的表节省时间
int mylog2[N];
void init(){
//log2不存在值为0的情况，避免报错
mylog2[0]=-1;
for (int i=1;i<=N;i++)mylog2[i]=mylog2[i>>1]+1;
for (int i=1;i<=n;i++)
{
//每个点长度为1时，最大公因数为自身
dp_max[i][0]=a[i];
}
//直接拿取n的Log2的值
int m=mylog2[n];
for (int k=1;k<=m;k++)
{
for (int s=1;s+(1<<k)<=n+1;s++)
{
dp_max[s][k]=__gcd(dp_max[s][k-1],dp_max[s+(1<<(k-1))][k-1]);
}
}
}
//计算区间
int query(int l,int r){
//区间长度
int k=mylog2[r-l+1];
//将区间截取两段，每次截取小于长度的2^k值
int newl=r-(1<<k)+1;
//比较两段的最大公因数
int x=__gcd(dp_max[l][k],dp_max[newl][k]);
return x;
}
int main() {
cin >>n>>q;
for (int i=1;i<=n;i++)cin >>a[i];
init();
for (int i=1;i<=q;i++)
{
int l,r;
cin >>l>>r;
cout <<query(l,r)<<"\n";
}
return 0;
}
查看18道真题和解析
