题目链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1174
RMQ的入门模板题...
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define maxn 10005
using namespace std;
int n,m;
int pre[maxn][25];
void ST(){
for(int j = 1; (1<<j) <= n; j++){
for(int i = 1; (i + (1<<j) - 1) <= n; i++){
pre[i][j] = max(pre[i][j-1], pre[i + (1 << (j-1) )][j-1]);
}
}
}
void RMQ(int l,int r){
int k = (int)(log(r-l+1.0)/log(2.0));
int ans = max(pre[l][k],pre[r - (1<<k) + 1][k]);
printf("%d\n",ans);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&pre[i][0]);
}
ST();
scanf("%d",&m);
while(m--){
int x,y;
scanf("%d%d",&x,&y);
x++;y++;
RMQ(x,y);
}
return 0;
}