ACM_最值差（线段树区间查询最值）

Problem Description:

给定N个数A1A2A3A4...AN.求任意区间Ai到Aj中的最大数与最小数之差。

Input:

输入包含多组测试，每组测试的第一行是两个数N(1<=N<=50000)和M（1<=M<=100000)，第二行是N个数A1到AN（1<=Ai<=10000）;接下来M行输入M个询问，每个询问包含两个数Ai,Aj。

Output:

对于每组测试，输出每个询问的答案。

Sample Input:

6 3

1 7 3 4 2 5

1 5

4 6

2 2

Sample Output:

6

3

0
解题思路：基本操作：线段树区间查询最值，时间复杂度大概为O(nlogn)。
AC代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int a,b,n,m,s[maxn];

 struct NODE{int maxval,minval;}t[maxn<<];

 void build(int l,int r,int x){//建树

     int mid=(l+r)>>;

     if(l==r){t[x].maxval=t[x].minval=s[mid];return;}

     build(l,mid,x<<);

     build(mid+,r,x<<|);

     t[x].maxval=max(t[x<<].maxval,t[x<<|].maxval);//父节点的值为左右孩子的最大值

     t[x].minval=min(t[x<<].minval,t[x<<|].minval);//父节点的值为左右孩子的最小值

 }

 int query1(int l,int r,int x){//查询区间最大值

     if(a<=l&&b>=r)return t[x].maxval;

     else{

         int mid=(l+r)>>;

         if(b<=mid)return query1(l,mid,x<<);

         else if(a>mid)return query1(mid+,r,x<<|);

         else return max(query1(l,mid,x<<),query1(mid+,r,x<<|));

     }

 }

 int query2(int l,int r,int x){//查询区间最小值

     if(a<=l&&b>=r)return t[x].minval;

     else{

         int mid=(l+r)>>;

         if(b<=mid)return query2(l,mid,x<<);

         else if(a>mid)return query2(mid+,r,x<<|);

         else return min(query2(l,mid,x<<),query2(mid+,r,x<<|));

     }

 }

 int main(){

     while(~scanf("%d %d",&n,&m)){

         for(int i=;i<=n;++i)scanf("%d",&s[i]);

         memset(t,,sizeof(t));//清0

         build(,n,);//建树

         while(m--){

             scanf("%d %d",&a,&b);

             printf("%d\n",query1(,n,)-query2(,n,));

         }

     }

     return ;

 }