学步园

思路：又是一道经典的线段树 比前面的两道要简单，没有更新操作

//2416K   
1579MS

#include <stdio.h>
#define M 50005

struct data
{
    int
l,r;
    int
tall,shor;
}line[3*M];
int num[M];
int min (int a,int b)
{
    return a
> b?b:a;
}
int max (int a,int b)
{
    return a
> b?a:b;
}
int low,hei;
void BuildTree(int left,int right,int u)
{
    line[u].l =
left;
    line[u].r =
right;
    if
(line[u].l == line[u].r)
    {
       
line[u].tall = num[left];
       
line[u].shor = num[left];
       
return ;
    }
    int mid =
(line[u].l+line[u].r)/2;
   
BuildTree(left,mid,2*u);
   
BuildTree(mid+1,right,2*u+1);
    line[u].tall
= max (line[2*u].tall,line[2*u+1].tall);
    line[u].shor
= min (line[2*u].shor,line[2*u+1].shor);
   
}
void query (int left,int right,int u)
{
    if
(line[u].l == left&&line[u].r ==
right)
    {
       
low = min (low,line[u].shor);
       
hei = max (hei,line[u].tall);
       
return ;
    }
    int mid =
(line[u].l + line[u].r)/2;
    if (right
<= mid)
       
query (left,right,2*u);
    else if
(left >= mid + 1)
       
query (left,right,2*u+1);
    else
    {
       
query(left,mid,2*u);
       
query (mid+1,right,2*u+1);
    }
}
int main ()
{
    int
n,m,a,b;
    scanf
("%d%d",&n,&m);
    for (int i =
1;i <= n;i ++)
       
scanf ("%d",&num[i]);
   
BuildTree(1,n,1);
    while (m
--)
    {
       
scanf ("%d%d",&a,&b);
       
low = 1000001;
       
hei = 0;
       
query (a,b,1);
       
printf ("%d\n",hei - low);
    }
    return
0;
}