Balanced Lineup---poj3264线段树基础

题目链接

求对应区间最大值与最小值的差；

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 0xfffffff
#define N 50010
using namespace std;

#define Lson r<<1
#define Rson r<<1|1

struct SegTree
{
    int L, R, Min, Max;
    int mid()
    {
        return (L+R)>>1;
    }
}a[N*4];
int MIN,MAX;
void BuildSegTree(int r, int L, int R)
{
    a[r].L = L, a[r].R = R;
    if(L == R)
    {
        scanf("%d", &a[r].Max);
        a[r].Min = a[r].Max;
        return;
    }
    BuildSegTree(Lson, L, a[r].mid());
    BuildSegTree(Rson, a[r].mid()+1, R);

    a[r].Max = max(a[Rson].Max, a[Lson].Max);
    a[r].Min = min(a[Rson].Min, a[Lson].Min);
   // a[r].ans = a[r].Max - a[r].Min;
}
void Query(int r, int L, int R)
{
    if(a[r].L == L && a[r].R == R)
    {
        MAX=max(MAX, a[r].Max);
        MIN=min(MIN, a[r].Min);
        return ;
    }
    if(L>a[r].mid())
        Query(Rson, L ,R);
    else if(R <= a[r].mid())
        Query(Lson, L, R);
    else
    {
        Query(Lson, L, a[r].mid());
        Query(Rson, a[r].mid()+1, R);
    }
}
int main()
{
    int n, m, L, R;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        BuildSegTree(1, 1, n);
        while(m--)
        {
            MIN=INF;
            MAX=-1;
            scanf("%d%d", &L,&R);
            Query(1, L, R);
            printf("%d
", MAX-MIN);
        }
    }
    return 0;
}