POJ 3264 Balanced Lineup （线段树查找最大最小值）

http://poj.org/problem?id=3264

题意：给你一个长度为n的序列a[N] （1 ≤ N ≤ 50000），询问Q(1 ≤ Q ≤ 200000) 次，每次输出【L, R】区间最大值与最小值的差是多少。

只需把模板的求和改成求最大和最小即可

#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <queue>
using namespace std;
const int maxn =  1e5+10  ;
const int inf =    0x3f3f3f3f;

struct node{
    int l,r;
    int add;
    int sum;
    int mx;
    int mn;
}tree[maxn<<2];

int kase=0;
int n,m,t;
int a,b,c;
int val = 1;
int ans = 0;
int mx,mn;
void pushup(int k)
{
    //tree[k].sum = tree[k<<1].sum+tree[k<<1|1].sum;
    tree[k].mx = max(tree[k<<1].mx,tree[k<<1|1].mx);
    tree[k].mn = min(tree[k<<1].mn,tree[k<<1|1].mn);
}

void build(int l,int r,int k)
{
    tree[k].l = l;  tree[k].r = r; 
    if(l == r){scanf("%d",&tree[k].sum); tree[k].mn = tree[k].mx = tree[k].sum; return; }
    int mid = (l+r)>>1;
    build(l,mid,k<<1);
    build(mid+1,r,k<<1|1);
    pushup(k);
}

void query(int k)
{
    if(a <= tree[k].l && b >= tree[k].r)
    {
      mx = max(mx,tree[k].mx);
      mn = min(mn,tree[k].mn);
      return ;
    }

    int mid = (tree[k].l+tree[k].r)>>1;
    if(a <= mid){ query(k<<1);}
    if(b > mid){ query(k<<1|1);}
}
int main()
{
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    build(1,n,1);
    while(m--)
    {
      scanf("%d%d",&a,&b);
      mx = -1;
      mn = inf;
      query(1);
      ans = mx -mn;
      printf("%d
",ans);
    }
  }
}