题目描述

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

思路

一个区间求最值的问题，很明显用线段树就可以水过了

#include 
#define maxn 50001
int a[maxn];
int ma(int x, int y)
{
    return x > y;
}
int mi(int x, int y)
{
    return x < y;
}
struct tree
{
    int x, min, max;
}e[maxn * 4];
int tt = 0, maxx = 0, minn = 0x7fffffff;
int read()
{
    int x = 0; char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar();
    while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch -'0'; ch = getchar();}
    return x;
}
int make(int p, int l, int r)
{
    if (l == r) 
    {
        tt++;
        e[p].x = e[p].max = e[p].min = a[tt];
        return 0;
    }   
    int m = (l + r) >> 1;
    make(p << 1, l, m);
    make(p << 1 | 1, m + 1, r);
    e[p].max = e[p << 1].max > e[p << 1 | 1].max ? e[p << 1].max : e[p << 1 | 1].max;
    e[p].min = e[p << 1].min < e[p << 1 | 1].min ? e[p << 1].min : e[p << 1 | 1].min;
}
int count(int p, int l, int r, int x, int y)
{
    if (l == x && r == y)
    {
        maxx = maxx > e[p].max ? maxx : e[p].max;
        minn = minn < e[p].min ? minn : e[p].min;
        return 0;
    }
    int m = (l + r) >> 1;
    if (y <= m) count(p << 1, l, m, x ,y);
    else if (m < x) count(p << 1 | 1, m + 1, r, x, y);  
    else
    {
        count(p << 1, l, m, x, m);
        count(p << 1 | 1, m + 1, r, m + 1, y);
    }
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        a[i] = read();

    make(1, 1, n);

    for (int i = 1; i <= m; i++)
    {
        int x = read(), y = read();
        count(1, 1, n, x, y);
        printf("%d\n", maxx - minn);
        maxx = 0; 
        minn = 0x7fffffff;
    }
}