RMQ
如题:作用是询问区间最大最小值问题
步骤:
1.定义
a[i]表示数列的数
lg数组是一个辅助数组,用于快速计算查询区间的长度对应的k值。具体来说,lg[i]表示以2为底,i的对数。在C++中,可以使用lg2函数来计算以2为底的对数
f[i][j]表示从a[i]到a[i+2^i-1]这个范围内的最大值,也就是以a[i]为起点连续2^i个数的最大值
2.初始化
初始化lg[0] = -1,这样才能使lg[1] = 0
预处理出长度为1-n的lg值
计算f[i][j]
void rmq() { lg[0] = -1; for(int i=1;i<=n;i++) f[i][0] = a[i],lg[i] = lg[i>>1]+1; //预处理出长度为1-n的lg值 for(int j=1;j<=lgn;j++) //计算f[i][j] for(int i=1;i+(1<<j)-1<=n;i++) //区间边界不超过n f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]); }
3.询问
对于求区间[x,y]的最大值,直接按照下面的表达式计算即可
s = lg[y-x+1]
ans = max(f[x][s],f[y-(1<<s)+1][s])
int s = lg[y-x+1]; //求lg2(y-x+1)下取整的值 printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s]));
6570: 数列区间最大值
描述
输入一串数字,给你 M 个询问,每次询问就给你两个数字 X,Y,要求你说出 X 到 Y 这段区间内的最大数。
输入
第一行两个整数 N,M 表示数字的个数和要询问的次数;
接下来一行为 N 个数;
接下来 M 行,每行都有两个整数 X,Y。
对于全部数据,1≤N≤105,1≤M≤106,1≤X≤Y≤N。数字不超过 C/C++ 的 int 范围。
输出
输出共 M 行,每行输出一个数。
样例输入
10 2
3 2 4 5 6 8 1 2 9 7
1 4
3 8
样例输出
5
8
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N = 1e5+10,inf = 0x3f3f3f3f,lgn = 20; int lg[N],f[N][lgn+5],a[N]; int n,m,x,y; void rmq() { lg[0] = -1; for(int i=1;i<=n;i++) f[i][0] = a[i],lg[i] = lg[i>>1]+1; //预处理出长度为1-n的lg值 for(int j=1;j<=lgn;j++) //计算f[i][j] for(int i=1;i+(1<<j)-1<=n;i++) //区间边界不超过n f[i][j] = max(f[i][j-1],f[i+(1<<j-1)][j-1]); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); rmq(); //预处理rmq while(m--) { scanf("%d%d",&x,&y); int s = lg[y-x+1]; //求lg2(y-x+1)下取整的值 printf("%d\n",max(f[x][s],f[y-(1<<s)+1][s])); } return 0; }