题解|#区间最大值# 蓝桥

st表模板题

#include<bits/stdc++.h>
using namespace std;
const int M=5e5+5;
int a[M]; int st[M][21];
int getMax(int l,int r){
  int k=log2(r-l+1);
  return max(st[l][k],st[r-(1<<k)+1][k]);
}
int main(){
  int n,q;
  cin>>n>>q;
  for(int i=1;i<=n;i++){
    cin>>a[i];
    st[i][0]=a[i];
  }
  for(int i=1;i<=20;i++){
    for(int j=1;j<=n;j++){
      if(j+(1<<i)-1<=n)
        st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]);
    }
  }
  for(int i=1;i<=q;i++){
    int l,r; cin>>l>>r;
    cout<<getMax(l,r)<<endl;
  }
  return 0;
}