poj 3264 Balanced Lineup

简单题，求一定范围内的最大数于最小数之差，用两个数组保存max和min就行了。
 1 #include <stdio.h>
 2 #include <string.h>
 3 #define N 50005
 4 #define INF 0x7fffffff
 5 int max[4*N],min[4*N];
 6 int D;
 7 int Max(int a,int b)
 8 {
 9     return a>b ?a :b;
10 }
11 int Min(int a,int b)
12 {
13     return a<b ?a :b;
14 }
15 int query(int a,int b)
16 {
17     int i=D+a-1, j=D+b+1;
18     int mi=INF,ma=-INF;
19     for(; i+1 != j; i>>=1, j>>=1)
20     {
21         if(~i & 1)
22             mi = Min(mi,min[i^1]),
23             ma = Max(ma,max[i^1]);
24         if(j & 1)
25             mi = Min(mi,min[j^1]),
26             ma = Max(ma,max[j^1]);
27     }
28     return ma-mi;
29 }
30 int main()
31 {
32     int m,n,i,x,y;
33     while(~scanf("%d%d",&n,&m))
34     {
35         for(D = 1; D < n+2; D <<= 1);
36         memset(max,0xc3,sizeof(int)*2*D);
37         memset(min,0x3f,sizeof(int)*2*D);
38         for(i = 1; i <= n; i++)
39         {
40             scanf("%d",&max[D+i]);
41             min[D+i] = max[D+i];
42         }
43         for(i = D-1; i; i--)
44         {
45             max[i] = Max(max[i<<1],max[i<<1|1]);
46             min[i] = Min(min[i<<1],min[i<<1|1]);
47         }
48         while(m--)
49         {
50             scanf("%d%d",&x,&y);
51             printf("%d\n",query(x,y));
52         }
53     }
54     return 0;
55 }