ST表-RMQ模板

ST表-RMQ

#include<iostream>
#include<cstdio>
#define N 100000+5
using namespace std;
int f[N][20];
int n,m;
int a[N],log[N];
int main(){
	int l,r;
	scanf("%d%d",&n,&m);
	log[0]=-1;
	for(int i=1;i<=n;i++)
		scanf("%d",&f[i][0]);
	for(int i=1;i<=n;i++)
		log[i]=log[i>>1]+1;
	for(int i=1;i<=18;i++)
		for(int j=1;j+(1<<i)-1<=n;j++)
			f[j][i]=max(f[j][i-1],f[j+(1<<i-1)][i-1]);
	while(m--){
		scanf("%d%d",&l,&r);
		int lg=log[r-l+1];
		printf("%d\n",max(f[l][lg],f[r-(1<<lg)+1][lg]));
	}
	return 0;
}