ST表

占坑。

填坑。

ST表的应用：区间最大值。

因为线段树常数太大，所以我们可以采用ST表。

我们可以用$f_{i,j}$表示从$i$开始的第$2^j$个数的最大值。

那么就有$f_{i,0}=a_i$。因为$f_{i,0}$里边只有$a_i$一个数（$2^0=1$），所以。

接下来就是预处理的问题了。

我们可以把$[i,i+2^j]$区间拆成两个区间，即$[i,i+2^{j-1}-1],[i+2^{j-1},i+2^j]$

接下来就是查询的问题了。

我们假设查询的区间是$[l,r]$，那么查询的长度是$r-l+1$。我们设$k=\log_2(r-l+1)$

那么我们就可以针对左端点，右端点分别查询，也就是查$f_{l,k}$以及$f_{r-2^k+1,r}$的最大值。

代码：

#include<bits/stdc++.h>
#define ns "-1"
#define fs(i,x,y,z) for(ll i=x;i<=y;i+=z)
#define ft(i,x,y,z) for(ll i=x;i>=y;i+=z)
#define ll long long
#define ull unsigned long long
#define db double
#define ms(a,b) memset(a,b,sizeof(a))
#define sz(a) sizeof(a)
using namespace std;
const int rw[]={-1,0,1,0,-1,1,-1,1},cl[]={0,1,0,-1,-1,1,1,-1};
const int N=100001,inf=0x3f3f3f3f;
const int daynum[]={114514,31,28,31,30,31,30,31,31,30,31,30,31};
const db E=2.718281828459,pi=acos(-1.0),eps=0.0000000001;
inline int read(){
	int date=0,w=1;char c=0;
	while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date*w;
}

int n,f[N][22],q;
inline int qr(int l,int r){
	int k=log2(r-l+1);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main(){
	n=read(),q=read();
	fs(i,1,n,1) f[i][0]=read();
	fs(j,1,21,1){
		for(int i=1;(1<<j)-1+i<=n;i++){
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
		}
	}
	fs(i,1,q,1){
		int l=read(),r=read();
		printf("%d\n",qr(l,r));
	}
	return 0;
}