题目链接：http://acm.ocrosoft.com/problem.php?cid=1689&pid=1

题目描述：

每天,农夫 John 的N(1 <= N <= 50,000)头牛总是按同一序列排队. 有一天, John 决定让一些牛们玩一场飞盘比赛. 他准备找一群在对列中为置连续的牛来进行比赛. 但是为了避免水平悬殊,牛的身高不应该相差太大. John 准备了Q (1 <= Q <= 180,000) 个可能的牛的选择和所有牛的身高 (1 <= 身高 <= 1,000,000). 他想知道每一组里面最高和最低的牛的身高差别. 注意: 在最大数据上, 输入和输出将占用大部分运行时间.

输入：

* 第一行: N 和 Q. * 第2..N+1行: 第i+1行是第i头牛的身高.

 

 * 第N+2..N+Q+1行: 两个整数, A 和 B (1 <= A <= B <= N), 表示从A到B的所有牛.

输出：

*第1..Q行: 所有询问的回答 (最高和最低的牛的身高差), 每行一个.

样例输入：

6 3

1

7

3

4

2

5

1 5

4 6

2 2

样例输出：

6

3

0

题目类型：

RMQ

思路：这道题是一道RMQ模板题，当然和前面不同的是它要求的是最大值和最小值之差，因此我们要建立两个RMQ预处理内容，分别处理最大值和最小值

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int dp[N][25];

int dpm[N][25];

int a[N];

int n,m,x,y;

void RMQ_build()//预处理

{

    for(int i=1;i<=n;i++)

    {

        dpm[i][0]=a[i];//存最小值

        dp[i][0]=a[i];//存最大值

    }

    for(int j=1;(1<<j)<=n;j++)

    {

        for(int i=1;i+(1<<j)-1<=n;i++)

        {

            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);//找最大值

            dpm[i][j]=min(dpm[i][j-1],dpm[i+(1<<j-1)][j-1]);//找最小值

        }

    }

    return;

}

int RMQ_query(int l,int r)//查询返回最大值和最小值之差

{

    int k=log2(r-l+1);

    return max(dp[l][k],dp[r-(1<<k)+1][k])-min(dpm[l][k],dpm[r-(1<<k)+1][k]);

}

int main()

{

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

    }

    RMQ_build();

    for(int i=1;i<=m;i++)

    {

        scanf("%d %d",&x,&y);

        printf("%d\n",RMQ_query(x,y));

     }

 }