poj3264

                                    想看更多的解题报告: http://blog.csdn.net/wangjian8006/article/details/7870410
                                     转载请注明出处：http://blog.csdn.net/wangjian8006

题目大意：给出一串的数字，然后给出一个区间a b，输出从a到b的最大的数和最小的数的差

解题方法：线段树

用线段树求出从a到b的最小值与最大值，直接相减输出就可以了

[cpp] view plain copy

1. #include <iostream>  
2. using namespace std;  
3. #define MAXV 50100  
4. #define MAXT 1<<18  
5. #define max(a,b) a>b?a:b  
6. #define min(a,b) a>b?b:a  
7.   
8. int a[MAXV],TL[MAXT],TR[MAXT],TMAX[MAXT],TMIN[MAXT];  
9. //TL与TR代表结点v区间的左边与右边的数，这样方便查询  
10. //TMAX,TMIN，代表结点v的最大值与最小值  
11.   
12. void createTree(int v,int f,int t){  
13.     TL[v]=f;  
14.     TR[v]=t;  
15.     if(f==t){  
16.         TMAX[v]=a[f];  
17.         TMIN[v]=a[f];  
18.         return;  
19.     }  
20.   
21.     int mid=(f+t)>>1;  
22.     createTree(v<<1,f,mid);  
23.     createTree((v<<1)|1,mid+1,t);  
24.   
25.     TMAX[v]=max(TMAX[v<<1],TMAX[(v<<1)|1]);  
26.     TMIN[v]=min(TMIN[v<<1],TMIN[(v<<1)|1]);  
27. }  
28. int queryTree(int v,int L,int R,int flag){  
29.     if(L==TL[v] && R==TR[v]){  
30.         return (flag?TMIN[v]:TMAX[v]);  
31.     }  
32.   
33.     int mid=(TL[v]+TR[v])>>1;  
34.     if(R<=mid)  
35.         return queryTree(v<<1,L,R,flag);  
36.     else if(L>mid)  
37.         return queryTree((v<<1)|1,L,R,flag);  
38.     else{  
39.         if(flag) return min(queryTree(v<<1,L,mid,flag),queryTree((v<<1)|1,mid+1,R,flag));  
40.         else return max(queryTree(v<<1,L,mid,flag),queryTree((v<<1)|1,mid+1,R,flag));  
41.     }  
42. }  
43.   
44. int main(){  
45.     int N,Q,L,R,i;  
46.     while(scanf("%d%d",&N,&Q)!=EOF){  
47.         for(i=1;i<=N;i++)  
48.             scanf("%d",&a[i]);  
49.   
50.         createTree(1,1,N);  
51.         while(Q--){  
52.             scanf("%d%d",&L,&R);  
53.             printf("%d\n",queryTree(1,L,R,0)-queryTree(1,L,R,1));  
54.         }  
55.     }  
56.     return 0;  
57. }