[线段树]poj 3264

题意

      给出一串数字，m个询问，对于每次询问求出在区间[a,b]上最大值和最小值的差。

 

思路

    水线段树

 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax = 1000010;
struct{
    int r,l,bg,sm;
}node[3*nMax];
int num[nMax];
void build(int left ,int right ,int u){
    node[u].l = left;
    node[u].r = right;
    if(left == right){
        node[u].sm = num[right];
        node[u].bg = num[left];
        return;
    }
    int m = (left + right)>>1;
    build(left , m , u*2);
    build(m + 1 , right ,u*2 + 1);
    node[u].bg = max(node[u*2].bg ,node[u*2 + 1].bg);
    node[u].sm = min(node[u*2].sm ,node[u*2 + 1].sm);
}

int query1(int left ,int right ,int u){
    if(left == node[u].l &&right == node[u].r){
        return node[u].bg;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(right <= m){
        return query1(left ,right , u*2);
    }
    if(left >= m+1){
        return query1(left ,right , u*2 + 1);
    }
    int a = query1(left ,m , u*2);
    int b = query1(m + 1  ,right , u*2 + 1);
    return max(a ,b);
}

int query2(int left ,int right ,int u){
    if(left == node[u].l &&right == node[u].r){
        return node[u].sm;
    }
    int m = (node[u].l + node[u].r)>>1;
    if(right <= m){
        return query2(left ,right , u*2);
    }
    if(left >= m+1){
        return query2(left ,right , u*2 + 1);
    }
    int a = query2(left ,m , u*2);
    int b = query2(m + 1  ,right , u*2 + 1);
    return min(a ,b);
}
int main(){
    int n ,m ,i ,a ,b ,c ,d;
    while(scanf("%d%d",&n,&m)!=EOF){
        for(i = 1; i <= n; i++){
            scanf("%d",&num[i]);
        }
        build(1 ,n ,1);
        while(m--){
            scanf("%d%d",&a,&b);
            c = query1(a ,b ,1);
            d = query2(a ,b ,1);
            c -= d;
            printf("%d\n",c);
        }
    }
    return 0;
}