POJ_3264 Balanced Lineup 【线段树/ST表 + 区间查询】

一、题面

二、分析

　　典型的区间问题，没有更新只有查询。

　　可以用线段树，也可以用ST表，但ST表空间上可能会多点。

　　查询的时候需要注意的是，在判断区间是完全属于右子树还是左子树时，要根据建树的情况来选择，不然会出错。具体看代码

三、AC代码

 1 #include <cstdio>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <fstream>
 6 
 7 using namespace std;
 8 
 9 const int MAXN = 5e4 + 15;
10 const int INF = 2e8;
11 int Data[MAXN], Max, Min;
12 struct Node
13 {
14     int l, r;
15     int nMax, nMin;
16 }segTree[MAXN<<2];
17 
18 void Build(int p, int L, int R)
19 {
20     segTree[p].l = L;
21     segTree[p].r = R;
22     if(L == R)
23     {
24         segTree[p].nMax = segTree[p].nMin = Data[R];
25         return;
26     }
27     int mid = (L + R) >> 1;
28     Build(p<<1, L, mid);
29     Build(p<<1 | 1, mid + 1, R);
30     segTree[p].nMax = max(segTree[p<<1].nMax, segTree[p<<1|1].nMax);
31     segTree[p].nMin = min(segTree[p<<1].nMin, segTree[p<<1|1].nMin);
32 
33 }
34 
35 void Query(int v, int L, int R)
36 {
37     int l = segTree[v].l;
38     int r = segTree[v].r;
39     if(l == L && r == R)
40     {
41         //cout << l << " ---- " << r << " : ";
42         //cout << segTree[v].nMax << " -- " << segTree[v].nMin << endl;
43         Max = max(segTree[v].nMax, Max);
44         Min = min(segTree[v].nMin, Min);
45         return;
46     }
47     int mid = (l + r) >> 1;
48     //因为前面建树的时候是mid+1，所以这里必须是<不能有等于
49     if(L > mid)        
50     {
51         Query(v<<1 | 1, L, R);
52     }
53     else if(R <= mid)
54     {
55         Query(v<<1, L, R);
56     }
57     else
58     {
59         Query(v<<1, L, mid);
60         Query(v<<1 | 1, mid + 1, R);
61     }
62 }
63 
64 int main()
65 {
66     //freopen("input.txt", "r", stdin);
67     int N, Q;
68     while(scanf("%d %d", &N, &Q) != EOF)
69     {
70         int L, R;
71         for(int i = 1; i <= N; i++)
72             scanf("%d", &Data[i]);
73         Build(1, 1, N);
74         for(int i = 0; i < Q; i++)
75         {
76             Max = -INF, Min = INF;
77             scanf("%d %d", &L, &R);
78             Query(1, L, R);
79             printf("%d
", Max - Min);
80         }
81     }
82 }

 1 #include <cstdio>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <fstream>
 6 
 7 using namespace std;
 8 const int MAXN = 5e4 + 15;
 9 const int INF = 2e8;
10 int Data[MAXN];
11 int STmax[MAXN][30], STmin[MAXN][30];
12 int Logn[MAXN];
13 
14 void Pre_log()
15 {
16     Logn[1] = 0, Logn[2] = 1;
17     for(int i = 3; i < MAXN; i++) {
18         Logn[i] = Logn[i/2] + 1;
19     }
20 }
21 
22 void Pre_st(int N)
23 {
24     for(int i = 1; i <= N; i++) {
25         STmin[i][0] = STmax[i][0] = Data[i];
26     }
27     for(int j = 1; j <= Logn[N]; j++) {
28         for(int i = 1; i + (1<<j) - 1 <= N; i++) {
29             STmax[i][j] = max(STmax[i][j-1], STmax[i+(1<<(j-1))][j-1]);
30             STmin[i][j] = min(STmin[i][j-1], STmin[i+(1<<(j-1))][j-1]);
31         }
32     }
33 }
34 
35 int Query_min(int L, int R)
36 {
37     int k = Logn[R - L + 1];
38     return min(STmin[L][k], STmin[R-(1<<k)+1][k]);
39 }
40 
41 int Query_max(int L, int R)
42 {
43     int k = Logn[R - L + 1];
44     return max(STmax[L][k], STmax[R-(1<<k)+1][k]);
45 }
46 
47 int main()
48 {
49     //freopen("input.txt", "r", stdin);
50     int N, Q;
51     Pre_log();
52     while(scanf("%d %d", &N, &Q) != EOF)
53     {
54         int L, R;
55         for(int i = 1; i <= N; i++)
56             scanf("%d", &Data[i]);
57         Pre_st(N);
58         for(int i = 0; i < Q; i++)
59         {
60             int ansMax, ansMin;
61             scanf("%d %d", &L, &R);
62             ansMax = Query_max(L, R);
63             ansMin = Query_min(L, R);
64             printf("%d
", ansMax - ansMin);
65         }
66     }
67 }