题意 ：N头奶牛，Q次询问，然后给你每一头奶牛的身高，每一次询问都给你两个数，x y，代表着从x位置上的奶牛到y位置上的奶牛身高最高的和最矮的相差多少。
思路 ： 刚好符合RMQ的那个求区间最大最小值，所以用RMQ还是很方便的。就是一个RMQ的模板题，基本上书上网上都有。
#include <stdio.h> #include <string.h> #include <math.h> #include <iostream> const int maxn = 51000 ; int maxsum[maxn][20],minsum[maxn][20] ; int a[maxn] ; int N,Q ; using namespace std ; void Init() { for(int i = 1 ; i <= N ; i++) { scanf("%d",&a[i]) ; maxsum[i][0] = a[i] ; minsum[i][0] = a[i] ; } } void RMQ() { int k = (int )(log((double)N)/log(2.0)) ; for(int j = 1 ; j <= k ; j++) for(int i = 1 ; i <= N ; i++) if(i + (1 << j) - 1 <= N ) { maxsum[i][j] = max(maxsum[i][j-1],maxsum[i + (1 << (j-1))][j-1]) ; minsum[i][j] = min(minsum[i][j-1],minsum[i + (1 << (j-1))][j-1]) ; } } int main() { while(~scanf("%d %d",&N,&Q)) { Init() ; RMQ() ; int x,y ; for(int i = 1 ; i <= Q ; i++) { scanf("%d %d",&x,&y) ; int k = (int)(log((double)(y-x+1))/log(2.0)) ; int minn = min(minsum[x][k],minsum[y-(1<<k)+1][k]) ; int maxx = max(maxsum[x][k],maxsum[y-(1<<k)+1][k]) ; printf("%d\n",maxx-minn) ; } } return 0 ; }
原文：http://www.cnblogs.com/luyingfeng/p/3567073.html
