POJ 3264：Balanced Lineup（区间最值查询ＳＴ表＆线段树）

Balanced Lineup

Time Limit: 5000MS		Memory Limit: 65536K
Total Submissions: 75294		Accepted: 34483
Case Time Limit: 2000MS

Description

For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

Input

Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.

Output

Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.

Sample Input

Sample Output

6
3
0

题意

查询区间内最大值和最小值的差值

解决

解法一：ＳＴ表

通过O(n*log(n))的预处理后，在O(1)的时间内查询出区间最值。

预处理的本质是DP，定义一个dp数组dp[i][j]，dp[i][j]表示：从第i个数起，连续2^j个数的最值，可以很容易得到：dp[i][0]就是第i个数的本身

接下来可以得到转移方程：dp[i][j]=max(dp[i][j-1],dp[i+2^(j-1)][j-1])

然后我们可以通过预处理求出所有位置的dp数组的值

在查询的时候，先算出所求区间的长度对2取对数，即求出上述方程中的j，然后用方程O(1)查询即可

解法二：线段树

代码

ST表

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cmath>
 4 #define ll long long
 5 #define ull unsigned long long
 6 #define ms(a,b) memset(a,b,sizeof(a))
 7 const int inf=0x3f3f3f3f;
 8 const ll INF=0x3f3f3f3f3f3f3f3f;
 9 const int maxn=1e6+10;
10 const int mod=1e9+7;
11 const int maxm=1e3+10;
12 using namespace std;
13 // rmq[i][j]表示从ｉ开始的第2^i位上的最大/最小值
14 // rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1])
15 int rmq_max[maxn][30];
16 int rmq_min[maxn][30];
17 int a[maxn];
18 int main(int argc, char const *argv[])
19 {
20     #ifndef ONLINE_JUDGE
21         freopen("/home/wzy/in.txt", "r", stdin);
22         freopen("/home/wzy/out.txt", "w", stdout);
23         srand((unsigned int)time(NULL));
24     #endif
25     ios::sync_with_stdio(false);
26     cin.tie(0);
27     int n,q;
28     cin>>n>>q;
29     for(int i=1;i<=n;i++)
30         cin>>a[i],rmq_min[i][0]=a[i],rmq_max[i][0]=a[i];
31     for(int j=1;(1<<j)<=n;j++)
32         for(int i=1;i+(1<<(j-1))-1<=n;i++)
33             rmq_min[i][j]=min(rmq_min[i][j-1],rmq_min[i+(1<<(j-1))][j-1]),rmq_max[i][j]=max(rmq_max[i][j-1],rmq_max[i+(1<<(j-1))][j-1]);
34     while(q--)
35     {
36         int x,y;
37         cin>>x>>y;
38         int z=(int)(log(y-x+1)/log(2));
39         int ans=max(rmq_max[x][z],rmq_max[y-(1<<z)+1][z])-min(rmq_min[x][z],rmq_min[y-(1<<z)+1][z]);
40         cout<<ans<<"
";
41     }
42     #ifndef ONLINE_JUDGE
43         cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
44     #endif
45     return 0;
46 }

线段树

不太会线段树，代码略丑

 1 #include <iostream>
 2 #include <algorithm>
 3 #define ll long long
 4 #define ull unsigned long long
 5 #define ms(a,b) memset(a,b,sizeof(a))
 6 const int inf=0x3f3f3f3f;
 7 const ll INF=0x3f3f3f3f3f3f3f3f;
 8 const int maxn=1e6+10;
 9 const int mod=1e9+7;
10 const int maxm=1e3+10;
11 using namespace std;
12 int a[maxn];
13 struct wzy
14 {
15     int value_min,value_max;
16 }p[maxn];
17 inline int lson(int p){return p<<1;}
18 inline int rson(int p){return p<<1|1;}
19 inline void push_max(int o)
20 {
21     p[o].value_max=max(p[lson(o)].value_max,p[rson(o)].value_max);
22 }
23 inline void push_min(int o)
24 {
25     p[o].value_min=min(p[lson(o)].value_min,p[rson(o)].value_min);
26 }
27 void build(int o,int l,int r)
28 {
29     if(l==r)
30     {
31         p[o].value_min=p[o].value_max=a[l];
32         return ;
33     }
34     int mid=(l+r)>>1;
35     build(lson(o),l,mid);
36     build(rson(o),mid+1,r);
37     push_max(o);
38     push_min(o);
39 }
40 int res,res1;
41 int query_min(int nl,int nr,int l,int r,int o)
42 {
43     if(nl<=l&&nr>=r)
44         return min(res,p[o].value_min);
45     int mid=(l+r)>>1;
46     if(nl<=mid)
47         res=query_min(nl,nr,l,mid,lson(o));
48     if(nr>mid)
49         res=query_min(nl,nr,mid+1,r,rson(o));
50     return res;
51 }
52 int query_max(int nl,int nr,int l,int r,int o)
53 {
54     if(nl<=l&&nr>=r)
55         return max(res1,p[o].value_max);
56     int mid=(l+r)>>1;
57     if(nl<=mid)
58         res1=query_max(nl,nr,l,mid,lson(o));
59     if(nr>mid)
60         res1=query_max(nl,nr,mid+1,r,rson(o));
61     return res1;
62 }
63 int main(int argc, char const *argv[])
64 {
65     #ifndef ONLINE_JUDGE
66         freopen("/home/wzy/in.txt", "r", stdin);
67         freopen("/home/wzy/out.txt", "w", stdout);
68         srand((unsigned int)time(NULL));
69     #endif
70     ios::sync_with_stdio(false);
71     cin.tie(0);
72     int n,q;
73     cin>>n>>q;
74     for(int i=1;i<=n;i++)
75         cin>>a[i];
76     build(1,1,n);
77     int x,y;
78     while(q--)
79     {
80         cin>>x>>y;
81         res=inf;res1=0;
82         cout<<query_max(x,y,1,n,1)-query_min(x,y,1,n,1)<<"
";
83     }
84     #ifndef ONLINE_JUDGE
85         cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
86     #endif
87     return 0;
88 }

View Code