模板-st表

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int a[100100],logn[100100],st[100100][35],doing[36],n,m;
void (){
    logn[1]=0;
   logn[2]=1;
   for(int i=3;i<=n;i++) logn[i]=logn[i>>1]+1;
   int j=0,cnt=1;
  doing[0]=1;
  while(cnt<=n){
       cnt<<=1;
       j++;
     doing[j]=cnt;
    }
    for(int i=1;i<=n;i++){
      int j=0,k=i-1;
      st[i][0]=a[i];
       while(k>0){
          j++;
         st[i][j]=max(st[i][j-1],st[i-doing[j-1]][j-1]);
          k-=doing[j];
     }
    }
}
void ask(int l,int r){
   int len=logn[r-l+1];
    int ret=max(st[l+doing[len]-1][len],st[r][len]);
    printf("%dn",ret);
}
int main(){
 scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++) scanf("%d",&a[i]);
  init_st();
   for(int i=1;i<=m;i++){
      int l,r;
        scanf("%d%d",&l,&r);
       ask(l,r);
    }
    return 0;
   }