2025年12月14日(st,倍增笔记)
2025-12-14 17:07:54
发布于：广东
25阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
//动态规划
//记忆化
//区间最大值问题
//1 2 3 4 5 6 7
//4 5 6 7 2 4 5 a[N];
//记忆化数组
//arr[l][r]==>区间[l,r],最大值
//当l==r?arr[l][r]=a[l]=a[r];
//arr[l][l]=a[l];
//arr[l][l+1]=max(a[l],a[l+1]);
//arr[l][l+2]=max(ans[l][l+1],a[l+2]);
//arr[l][r]=max(arr[l][r-1],a[r])==>状态转移方程
2.
// arr[inx][len];从起点inx计算len个数字的中的最大值
//arr[inx][1]=a[inx];
//arr[inx][len]=max(arr[inx][len-1],a[inx+len-1]);
//
3.
//arr[inx][x];从起点inx计算2^x个数字中的最大值
//arr[inx][0]=a[inx];
//arr[inx][1]=max(a[inx],a[inx+1]) //2^1=2两个数字
//arr[inx][2]=max(a[inx][1],a[inx+2][1]) //2^2=4两个数字
//arr[inx][3]=max(a[inx][2],a[inx+4][2]) //2^3=8两个数字
//arr[inx][x]=max(a[inx][x-1],a[inx+2^(x-1)][x-1]);==>>状态转移方程
//[l,r]
//len=r-l+1;
//10
#include<bits/stdc++.h>
using namespace std;
const int logn=21;
const int maxn=1e5+10;
int f[maxn][logn+1],Logn[maxn+1];
int n,m;
//f[i][j]表示区间[i,i+2^j-1]的最大值
void pre(){
Logn[1]=0;
Logn[2]=1;
for(int i=3;i<=maxn;i++)
Logn[i]=Logn[i/2]+1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&f[i][0]);
pre();
for(int j = 1;j <= logn;j++)
for(int i = 1;i+(1<<j)-1 <= n;i++)
f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
int s=Logn[y-x+1];
printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
}
return 0;
} 
有帮助，赞一个