POJ 3264 Balanced Lineup

题目链接： http://poj.org/problem?id=3264

题目大意：求区间内最大值与最小值之差

思路：经典问题，此外还可用线段树做，维护一个变量即可。

代码（）：

#include <cstdio>
#include <cmath>
#include <cctype>
#include <cstring>
#include <iostream>
static const int MAXN=100050;
static const int lim=25;
int k,n,q,ql,qr,f1[MAXN][lim],f2[MAXN][lim];
inline int read()
{
  int x=0;bool sign=false;
  char alpha=0;
  while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
  while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
  return sign?-x:x;
}
inline int get_max(int a,int b){return a>b?a:b;}
inline int get_min(int a,int b){return a<b?a:b;}
inline void make_st()
{
  int t=log2(n);
  for(int j=1;j<=t;j++)
    for(int i=1;i<=n-(1<<j)+1;i++)
    {
    	f1[i][j]=get_max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
    	f2[i][j]=get_min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
    }
}
int main()	
{
  n=read();q=read();
  memset(f1,-1,sizeof(f1));
  memset(f2,127/2,sizeof(f2));
  for(int i=1;i<=n;i++) f1[i][0]=f2[i][0]=read();
  make_st();
  for(int i=1;i<=q;i++)
  {
    ql=read();qr=read();
    k=log2(qr-ql+1);
    printf("%d\n",get_max(f1[ql][k],f1[qr-(1<<k)+1][k])-get_min(f2[ql][k],f2[qr-(1<<k)+1][k]));
  }
  return 0;
}

代码（线段树）：

#include <cstdio>
#include <cctype>
#include <cstring> 
#include <iostream>
#define ls p<<1
#define rs p<<1|1
typedef long long ll;
static const int MAXN=50050;
static const int INF=2147483647;
struct node
{
  ll Max,Min;
}a[MAXN<<2];
int n,m,ql,qr;
inline int read()
{
  int x=0;bool sign=false;
  char alpha=0;
  while(!isdigit(alpha)) sign|=alpha=='-',alpha=getchar();
  while(isdigit(alpha)) x=(x<<1)+(x<<3)+(alpha^48),alpha=getchar();
  return sign?-x:x;
}
inline int get_max(int a,int b){return a>b?a:b;}
inline int get_min(int a,int b){return a<b?a:b;}
struct Segment_Tree
{
  inline void push_up(int p)
  {
    a[p].Max=get_max(a[ls].Max,a[rs].Max);
    a[p].Min=get_min(a[ls].Min,a[rs].Min); 
  }
  void build(int p,int l,int r)
  {
    if(l==r)
    {
      a[p].Max=a[p].Min=read();
      return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    push_up(p);
  }
  node query(int p,int l,int r)
  {
    if(ql<=l&&qr>=r) return a[p];
    ll mid=(l+r)>>1,Max=-INF,Min=INF;
    node t;
    if(ql<=mid) t=query(ls,l,mid),Min=get_min(Min,t.Min),Max=get_max(Max,t.Max);;
    if(qr>mid) t=query(rs,mid+1,r),Min=get_min(Min,t.Min),Max=get_max(Max,t.Max);;
    t.Max=Max,t.Min=Min;
    return t;
  }
}Tree;
int main()
{
  n=read();m=read();
  Tree.build(1,1,n);
  for(int i=1;i<=m;i++)
  {
    ql=read();qr=read();
    node x=Tree.query(1,1,n);
    printf("%lld\n",x.Max-x.Min);
  }
  return 0;
}