题目描述
从前有个人名叫 WNB,他有着天才般的记忆力,他珍藏了许多许多的宝藏。
在他离世之后留给后人一个难题(专门考验记忆力的啊!),如果谁能轻松回答出这个问题,便可以继承他的宝藏。
题目是这样的:给你一大串数字(编号为 1 到 N,大小可不一定哦!),在你看过一遍之后,它便消失在你面前,随后问题就出现了,给你 M 个询问,每次询问就给你两个数字 A,B,要求你瞬间就说出属于 A 到 B 这段区间内的最大数。
一天,一位美丽的姐姐从天上飞过,看到这个问题,感到很有意思(主要是据说那个宝藏里面藏着一种美容水,喝了可以让这美丽的姐姐更加迷人),于是她就竭尽全力想解决这个问题。
但是,她每次都以失败告终,因为这数字的个数是在太多了!
于是她请天才的你帮他解决。如果你帮她解决了这个问题,可是会得到很多甜头的哦!
算法:RMQ(ST表)
时间复杂度:$Nlog(N)$
ST表(RMQ)主要解决区间最值的查询
C++代码
//RMQ问题:用于求解区间的最值问题
//本质是利用倍增的思想和DP的手段进行的预处理
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int N=200010;
const int M=20;
int w[N];
int f[N][M]; //状态表示的含义:以i开始,长度为1<<j这段区间的最值
int n,m;
void init()
{
//先枚举长度 再枚举起点
//保证在枚举长度比较大的区间之前 长度较小的区间已经被计算过
for(int j=0;j<M;j++){
for(int i=1;i+(1<<j)-1<=n;i++){
if(!j)f[i][j]=w[i];
else f[i][j]=max(f[i][j-1],f[i+(1<<j-1)][j-1]);
}
}
}
//区间最值查询
int query(int l,int r)
{
int len=r-l+1;
int k=log(len)/log(2);
//可以确保覆盖整个区间
return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
init();
cin>>m;
for(int i=1;i<=m;i++){
int l,r;
scanf("%d%d",&l,&r);
cout<<query(l,r)<<endl;
}
return 0;
}