poj 3264 Balanced Lineup

就是简单的线段树最大值减去最小值，这里没有单点更新

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=50005;
int num[maxn];
struct
{
    int l,r,maxx,minn;
}tree[4*maxn];
int max(int m, int n)
{
    if(m>n)
      return m;
    return n;
}
int min(int m,int n)
{
    if(m<n)
      return m;
    return n;
}
void build (int root, int l, int r)
{
    tree[root].l=l;
    tree[root].r=r;
    if(tree[root].l == tree[root].r)
      {
          tree[root].maxx=num[l];
          tree[root].minn=num[l];
          return;
      }
    int mid=(l+r)/2;
    build(2*root, l, mid);
    build(2*root+1, mid+1, r);
    tree[root].maxx=max(tree[2*root].maxx,tree[2*root+1].maxx);
    tree[root].minn=min(tree[2*root].minn,tree[2*root+1].minn);
}
/*void update(int root, int pos, int val)
{
    if(tree[root].l == tree[root].r&&tree[root].l==pos)
    {
        tree[root].sum=val;
        return;
    }
    int mid=(tree[root].l + tree[root].r)/2;
    if(pos <= mid)
        update(2*root, pos, val);
    else
        update(2*root+1, pos, val);
    tree[root].sum=max(tree[2*root].sum,tree[2*root+1].sum);
}*/
int query1(int root, int L, int R)
{
    int s;
    if(L == tree[root].l && R == tree[root].r)
      return tree[root].maxx;
    if(R <= tree[2*root].r)
       s=query1(2*root, L, R);
    else if(L >= tree[2*root+1].l)
       s=query1(2*root+1, L, R);
    else
    {
        s=max(query1(2*root, L, tree[2*root].r),query1(2*root+1, tree[2*root+1].l, R));
    }
    return s;
}
int query2(int root, int L, int R)
{
    int s;
    if(L == tree[root].l && R == tree[root].r)
      return tree[root].minn;
    if(R <= tree[2*root].r)
       s=query2(2*root, L, R);
    else if(L >= tree[2*root+1].l)
       s=query2(2*root+1, L, R);
    else
    {
        s=min(query2(2*root, L, tree[2*root].r),query2(2*root+1, tree[2*root+1].l, R));
    }
    return s;
}
char str[20];
int main()
{
    int t, m, n, cas=1, a, b,ans1,ans2;
    while(~scanf("%d%d",&m,&n))
    {
        for(int i=1; i<=m; i++)
        scanf("%d",&num[i]);
        build(1, 1, maxn);
        for(int i=1; i<=n; i++)
        {
            scanf("%d%d",&a,&b);
            ans1=query1(1,a,b);
            ans2=query2(1,a,b);
            cout<<ans1-ans2<<endl;
        }
    }
    return 0;
}