poj3264
Description
在每天挤奶的时候，农民约翰的N头牛（1≤n≤50000）总是排成一列。有一天，约翰决定与他的牛们一起玩一个极限飞盘游戏。为了简单起见，他将从奶牛队列里面选一定范围内的奶牛来玩这个游戏。然而所有的牛对这个游戏都很感兴趣。农民约翰列出了Q份名单（1≤Q≤200000）和每个奶牛的高度（1≤高度≤1000000）。对于每一份名单，他想你帮助他确定在每份名单中高度最高的奶牛与高度最低的奶牛的高度差是多少。
Input
第一行为N(1≤N≤50000)和Q(1≤Q≤200000)；从第2行到第N+1行，每行一个数字，表示第i头牛的高度(1≤height≤1000000)；从第N+2行到第N+Q+1行，每行两个整数A和B(1≤A≤B≤N)，表示从第A头牛到第B头牛的范围。
Output
从第一行到第Q行，每行一个整数，表示从第A头牛到第B头牛之间，最高牛与最矮牛的高度差。
Sample Input
6 3 1 7 3 4 2 5 1 5 4 6 2 2
Sample Output
6 3 0
裸的RMQ，维护区间最小值和最大值
但是有些细节需要注意。。
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 using namespace std;
6 const int MAXN=200001;
7 void read(int & n)
8 {
9 char c='+';int x=0;bool flag=0;
10 while(c<'0'||c>'9')
11 {c=getchar();if(c=='-')flag=1;}
12 while(c>='0'&&c<='9')
13 {x=x*10+(c-48);c=getchar();}
14 flag==1?n=-x:n=x;
15 }
16 int n,m;
17 int a[MAXN],maxrmq[MAXN][51],minrmq[MAXN][51];
18 int qmax(int l,int r)
19 {
20 int k=0;
21 while(l+(1<<(k+1))<=r+1)
22 k++;
23 return max(maxrmq[l][k],maxrmq[r-(1<<k)+1][k]);
24 }
25 int qmin(int l,int r)
26 {
27 int k=0;
28 while(l+(1<<(k+1))<=r+1)
29 k++;
30 return min(minrmq[l][k],minrmq[r-(1<<k)+1][k]);
31 }
32 int main()
33 {
34 read(n);read(m);
35 for(int i=1;i<=n;i++)
36 read(a[i]);
37 for(int i=1;i<=n;i++)
38 maxrmq[i][0]=minrmq[i][0]=a[i];
39 for(int j=1;j<=25;j++)
40 {
41 for(int i=1;i+(1<<j)<=n+1;i++)
42 {
43 maxrmq[i][j]=max(maxrmq[i][j-1],maxrmq[i+(1<<(j-1))][j-1]);
44 minrmq[i][j]=min(minrmq[i][j-1],minrmq[i+(1<<(j-1))][j-1]);
45 }
46 }
47 for(int i=1;i<=m;i++)
48 {
49 int x,y;
50 read(x);read(y);
51 printf("%d\n",qmax(x,y)-qmin(x,y));
52 }
53 return 0;
54 }本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-06-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录