#include<bits/stdc++.h>
using namespace std;
const int Maxn=100010,Maxm=25;
int a[Maxn],Logn[Maxn];
int f[Maxn][Maxm];  //f[x][2**k] 从第x位置开始(包括)，到2**k的位置的最大数
int n,m,x,y;
char ch;
int read(){//快读
    ch=getchar();
    int x=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x;
}

int main(){
   n=read();//数字个数
   m=read();//询问次数
   for(int i=1;i<=n;++i) a[i]=read();//f[i][0]=a[i]
   Logn[0]=-1;
   for(int i=1;i<=n;++i){
    Logn[i]=Logn[i>>1]+1;//处理区间最大值的k取值
    f[i][0]=a[i];//初始状态的赋值
   }
   int LogN=Logn[n];
   for(int k=1;k<=LogN;k++){//预处理(递推)
    for(int i=1;i+(1<<k)-1<=n;++i ){
        f[i][k]=max(f[i][k-1],f[i+(1<<(k-1))][k-1]);
    }//<=n 防止越界
   }
   while(m--){
    x=read();
    y=read();
    int j=Logn[y-x+1];//二叉树处理过的间距2**j
   printf("%d\n",(max(f[x][j],f[y+1-(1<<j)][j])));
   }
   return 0;
}

朴素题，我们用f[i][j]记录区间[i,i+2^j]的最大值，并初始化出每个点i到每个能对应的[i,i+2^j]区间的数。

对于每个区间[l,r]，只需要求出[l,r]之下最大的2的整次方数k，然后比较f[l][k]和f[r-2^k+1][k]即可。

复杂度O（nlogn），可过。

PS：线段树试过了爆掉了，树状数组也未能幸免，也许我写的太屑了的原因。。。printf和scanf可以用去掉流同步的cin和cout，也可以写快读应该都能过。

#include <bits/stdc++.h>
using namespace std;
const int LXB = 1e5+5;

int n,m;
int a[LXB],f[LXB][20];

int rmq(int l,int r)
{
    int k=0;
    while((1<<(k+1))<=(r-l+1))
        k++;
    return max(f[l][k],f[r-(1<<k)+1][k]);
}

int main()
{
    scanf("%d%d", &n, &m);
    int x,y;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        f[i][0] = a[i];
    }
    
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i+(1<<j)-1<=n; i++)
            f[i][j] = max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
    
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",rmq(x,y));
    }
    
    return 0;
}