测试地址：☞
【题目描述】
原题来自 USACO 2007 Jan. Gold
FJ 的 N 头牛总是按同一序列排队。有一天，FJ 决定让一些牛玩一场飞盘比赛。他准备找一群在对列中为置连续的牛来进行比赛，但是为了避免水平悬殊，牛的身高不应该相差太大。FJ 准备了 Q 个可能的牛的选择和所有牛的身高。他想知道每一组里面最高和最低的牛的身高差别。
【输入】
第一行：N 和 Q；
第二至第 N+1 行，第 i+1 行是第 i 头牛的身高 hi ；
第 N+2 至第 N+Q+1 行，每行两个整数 A 和 B，表示从 A 到 B 的所有牛。
【输出】
第一至第 Q 行，每行一个整数，表示对于询问的回答（即最高和最低的牛的身高差）。
【输入样例】
6 3 1 7 3 4 2 5 1 5 4 6 2 2【输出样例】
6 3 0【提示】
数据范围与提示：
对于全部数据，1≤N≤5×10^4,1≤Q≤1.8×10^5,1≤hi≤10^6,1≤A≤B≤N。
【AC代码】
#include<cstdio> #include<iostream> using namespace std; const int maxn=200007; int n,k,a[maxn]; int dp1[maxn][25], dp2[maxn][25]; void rmq_init(){ for(int i = 1; i <= n; i++){ dp1[i][0] = a[i]; dp2[i][0] = a[i]; } for(int j = 1; (1<<j) <= n; j++){ for(int i = 1; i+(1<<j)-1 <= n; i++){ dp1[i][j] = max(dp1[i][j-1], dp1[i+(1<<(j-1))][j-1]); dp2[i][j] = min(dp2[i][j-1], dp2[i+(1<<(j-1))][j-1]); } } } int rmq_max(int l, int r){ int k=0; while(1<<(k+1) < r-l+2) k++; return max(dp1[l][k],dp1[r-(1<<k)+1][k]); } int rmq_min(int l, int r){ int k=0; while(1<<(k+1) < r-l+2) k++; return min(dp2[l][k], dp2[r-(1<<k)+1][k]); } int main(){ scanf("%d%d", &n, &k); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); rmq_init(); while(k--){ int l, r; scanf("%d%d", &l, &r); printf("%d\n", rmq_max(l, r)-rmq_min(l, r)); } return 0; }
