RMQのSTアルゴリズムテンプレート

/*
ST  ：              。

           

   ：   F[i][j]    i    i+2^j-1        ,        2^j            2^(j-1)     

  1    i.....i+2^(j-1)-1     2   i+2^(j-1).....i+2^j-1

        F[i][j] =Max( F[i][j-1],F[i+2^(j-1)][j-1]，     F[i][0]=A[i].

               ，                     F[i][j].

 

  ：   [ i , j ]        d=(int) log2( j-i+1)   

    i    2^d      j 2^d        ，             

  i,j max= Max ( F[i][d] ,F[j-2^d+1,d])

 

  ：               。

                 
*/

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<iostream>
using namespace std;
const int MAXN = 100100;
int n,query;
int A[MAXN];
int FMin[MAXN][20],FMax[MAXN][20];

void Init(){
	int i,j;
	for(i=1;i<=n;i++)
		FMin[i][0]=FMax[i][0]=A[i];
	for(i=1;(1<<i)<=n;i++){   //            
		for(j=1;j+(1<<i)-1<=n;j++){   //     
			FMin[j][i]=min(FMin[j][i-1],FMin[j+(1<<(i-1))][i-1]);
			FMax[j][i]=max(FMax[j][i-1],FMax[j+(1<<(i-1))][i-1]);
		}
	} 
}

int Query(int l,int r){
	int k=(int)(log(double(r-l+1))/log((double)2));
	return max(FMax[l][k],FMax[r-(1<<k)+1][k]);
}
int main(){
	int i,a,b;
	scanf("%d %d",&n,&query);
	for(i=1;i<=n;i++) scanf("%d",&A[i]);
	Init();
	while(query--){
		scanf("%d %d",&a,&b);
		printf("%d
",Query(a,b));
	}
	return 0;
}