题目描述
静态求区间最值问题
样例
st表模板题
时间复杂度 mlogn
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
// #define int long long
#define endl '\n'
const int N=1e5+10;
int dp[N][50];
int a[N];
int ask(int l,int r)
{
int j=(int)log2(r-l+1);
return max(dp[l][j],dp[r-(1<<j)+1][j]);
}
signed main()
{
ios::sync_with_stdio(false);//卡cin
cin.tie(0);cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
//st 表预处理
for(int i=1;i<=n;i++) dp[i][0]=a[i];
for(int j=1;j<=log2(n);j++){
for(int i=1;i+(1<<j)-1<=n;i++){
dp[i][j]=max(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
}
}
int l,r;
while(m--){
cin>>l>>r;
cout<<ask(l,r)<<endl;
}
return 0;
}
求大佬教教