poj 3264 Balanced Lineup

点击打开链接poj3264

思路：线段树
分析：
1 要求区间的最大值和最小值的差值
2 建立一棵线段树，节点保存这个区间的最大值和最小值，然后写两个查询函数，一个返回最大值一个返回最小值，然后相减即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define MAXN 50010

int n , q;
int height[MAXN];
struct Node{
   int left;
   int right;
   int minNum;
   int maxNum;
};
Node node[4*MAXN];

//建立线段树
void buildTree(int left , int right , int pos){
    node[pos].left = left;
    node[pos].right = right;
    if(left == right){
       node[pos].minNum = height[left];
       node[pos].maxNum = height[left];
       return;
    }
    int mid = (left+right)>>1;
    buildTree(left , mid , pos<<1);
    buildTree(mid+1 , right , (pos<<1)+1);
    node[pos].minNum = min(node[pos<<1].minNum , node[(pos<<1)+1].minNum);
    node[pos].maxNum = max(node[pos<<1].maxNum , node[(pos<<1)+1].maxNum);
}

//查询最大值
int queryMax(int left , int right , int pos){
   if(node[pos].left == left && node[pos].right == right)
     return node[pos].maxNum;
   int mid = (node[pos].left+node[pos].right)>>1;
   if(right <= mid)
     return queryMax(left , right , pos<<1);
   else if(left > mid)
     return queryMax(left , right , (pos<<1)+1);
   else
     return max(queryMax(left , mid , pos<<1) , queryMax(mid+1 , right , (pos<<1)+1));
}

//查询最小值
int queryMin(int left , int right , int pos){
    if(node[pos].left == left && node[pos].right == right)
      return node[pos].minNum;
    int mid = (node[pos].left+node[pos].right)>>1;
    if(right <= mid)
       return queryMin(left , right , pos<<1);
    else if(left > mid)
       return queryMin(left , right , (pos<<1)+1);
    else
       return min(queryMin(left , mid , pos<<1) , queryMin(mid+1 , right , (pos<<1)+1));
}

int main(){
   while(scanf("%d%d" , &n , &q) != EOF){
       for(int i = 1 ; i <= n ; i++)
          scanf("%d" , &height[i]);
       buildTree(1 , n , 1);
       int left , right;
       for(int i = 0 ; i < q ; i++){
          scanf("%d%d" , &left , &right);      
          cout<<queryMax(left , right , 1)-queryMin(left , right , 1)<<endl;
       }
   }
   return 0;
}