RMQ（ST表）

#include<iostream>
#include<cstdio>
#include<cmath> 
using namespace std;
int N, M, a[100009], l, r, st[100009][20];
inline int read()
{
	int s=0, w=1; char ch=getchar();
	while( ch<'0' || ch>'9' ){ if(ch=='-') w=-1; ch=getchar(); }
	while(ch>='0' && ch<='9'){ s=s*10+ch-'0';	 ch=getchar(); }
	return s*w;
}
void pre()										//预处理求st表 
{
	for(register int i=1; i<=N; i++) st[i][0]=a[i];
	for(int k=1; (1<<k)<=N; k++)
		for(register int i=1; i<=N; i++)
		{
			if(i+(1<<k)-1>N) break;
			st[i][k]=max(st[i][k-1], st[i+(1<<(k-1))][k-1]);
		}
}
int maxf(int l, int r)							//区间划分与求值 
{
	if(l==r) return st[l][0];
	int t=log(r-l)/log(2);						//注意在Linux下log计算可能存在的潜在问题 
	return max(st[l][t], st[r-(1<<t)+1][t]);
}
int main()
{
	N=read(), M=read();
	for(register int i=1; i<=N; i++) a[i]=read();
	pre();
	for(register int i=1; i<=M; i++) l=read(), r=read(), printf("%d
", maxf(l, r));
	return 0;
}