Balanced Lineup(线段树)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N=1000010;
 6 struct node
 7 {
 8     int l,r;
 9     int Max,Min;
10 } Tree[N*4];
11 int h[N],max1=0,min1=N;
12 void build(int l,int r,int rt)
13 {
14     Tree[rt].l = l;
15     Tree[rt].r = r;
16     if (l==r)
17     {
18         Tree[rt].Max=Tree[rt].Min=h[r];
19         return ;
20     }
21     int mid = (l+r)>>1;
22     build(l,mid,rt<<1);
23     build(mid+1,r,rt<<1|1);
24     Tree[rt].Max=max(Tree[rt<<1].Max,Tree[rt<<1|1].Max);
25     Tree[rt].Min=min(Tree[rt<<1].Min,Tree[rt<<1|1].Min);
26 }
27 void Query(int l,int r,int rt)
28 {
29     if(Tree[rt].l==l&&Tree[rt].r==r)
30     {
31         max1=max(max1,Tree[rt].Max);
32         min1=min(min1,Tree[rt].Min);
33         return ;
34     }
35     int mid = (Tree[rt].l+Tree[rt].r)>>1;
36     if (r <= mid)
37         Query(l,r,rt<<1);
38     else if (l > mid)
39         Query(l,r,rt<<1|1);
40     else
41     {
42         Query(l,mid,rt<<1);
43         Query(mid+1,r,rt<<1|1);
44     }
45 }
46 int main()
47 {
48     int n,q;
49     while(~scanf("%d%d",&n,&q))
50     {
51         for (int i = 1; i <= n; i++)
52             scanf("%d",&h[i]);
53         build(1,n,1);
54         while(q--)
55         {
56             max1=-1,min1=N;
57             int l,r;
58             scanf("%d%d",&l,&r);
59             Query(l,r,1);
60             printf("%d\n",max1-min1);
61         }
62     }
63     return 0;
64 }