\(O(nlogn)\)预处理，\(O(1)\)查询。注意不要越界。

令 \(f[i][j]\) 表示 \([i,i+2^j-1]\) 的最大值。

显然， \(f[i][0]=a[i]\) 。

根据定义式，写出状态转移方程： \(f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])\) 。

我们可以这么理解：将区间 \([i,i+2^j-1]\) 分成相同的两部分

中点即为 \((i+(i+2^j-1))/2=i+2^{j-1}-1/2\)

所以 \([i,i+2^j-1]\) 可以分成 \([i,i+2^{j-1}-1]\) 和 \([i+2^j,i+2^j-1]\)

对于每个询问 \([x,y]\) ，我们把它分成两部分 \(f[x][s],f[y-2^s+1][s]\)

其中 \(s=log_2(y-x+1)\) ，虽然这两个区间有重叠，但是重叠不会影响区间的最大值。

---

#include 
    
     using namespace std;#define ll long long//既然使用ST表，就是要尽可能卡常inline int read() {    char c=getchar();    int x=0,f=1;    while(c<'0'||c>'9') {        if(c=='-')            f=-1;        c=getchar();    }    while(c>='0'&&c<='9') {        x=x*10+c-'0';        c=getchar();    }    return x*f;}class ST_Table {private:    static const int MAXLOGN=17;    static const int MAXN=100000;    int logn[MAXN+5];    int f[MAXN+5][MAXLOGN+1];public:    inline void init1() {        logn[1]=0;        for(int i=2; i<=MAXN; i++) {            logn[i]=logn[i/2]+1;        }    }    inline void init2(int n) {        //或者改成从数组中复制也可以        for(int i=1; i<=n; i++)            f[i][0]=read();        for(int j=1; j<=MAXLOGN; j++)            for(int i=1; i+(1<
     
      <=n; i++)                f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);    }    inline int range_max(int l,int r){        int s=logn[r-l+1];        return max(f[l][s],f[r-(1<