Balanced Lineup

Time Limit: 5000MS

 

Memory Limit: 65536K

Total Submissions: 75294

 

Accepted: 34483

Case Time Limit: 2000MS

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.

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.

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.

6 3
1
7
3
4
2
5
1 5
4 6
2 2

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)查询即可

代码

1 #include
2 #include
3 #include
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<>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<<"\n";
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
2 #include
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)<<"\n";
83 }
84 #ifndef ONLINE_JUDGE
85 cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl;
86 #endif
87 return 0;
88 }