【题目链接：NYOJ-119】
思路：转自 点我 ，讲的挺好。
1 #include <cstdio> 2 #include <math.h> 3 #define max(a,b) ((a>b)?a:b) 4 #define min(a,b) (a<b?a:b) 5 const int maxn=100010; 6 int h[maxn]; 7 int mx[maxn][20],mn[maxn][20]; 8 int n,q; 9 void rmq_init(){ 10 int i,j,t; 11 for(j=1;j<=n;j++) mx[j][0]=mn[j][0]=h[j]; 12 int m=floor(log((double)n)/log(2.0)); 13 for(i=1;i<=m;i++){ 14 for(j=1;j<=n;j++){ 15 t = j+(1<<(i-1)); 16 if(t<=n) mx[j][i]=max(mx[j][i-1],mx[t][i-1]); 17 else mx[j][i]=mx[j][i-1]; 18 } 19 } 20 for(i=1;i<=m;i++){ 21 for(j=1;j<=n;j++){ 22 t = j+(1<<(i-1)); 23 if(t<=n) mn[j][i]=min(mn[j][i-1],mn[t][i-1]); 24 else mn[j][i]=mn[j][i-1]; 25 } 26 } 27 } 28 int rmq(int l,int r){ 29 int m=floor(log((double)(r-l+1))/log(2.0)); 30 int a=max(mx[l][m],mx[r-(1<<m)+1][m]); 31 int b=min(mn[l][m],mn[r-(1<<m)+1][m]); 32 return a-b; 33 } 34 int main(){ 35 int i,l,r; 36 int T,C,L,R; 37 scanf("%d%d",&n,&q); 38 for(i = 1;i <= n;i++) 39 scanf("%d",&h[i]); 40 rmq_init(); 41 while(q--){ 42 scanf("%d%d",&L,&R); 43 printf("%d ",rmq(L,R)); 44 } 45 return 0; 46 }