poj3264

2018-06-17 22:21:29来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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 }

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:P1168 中位数

下一篇:P1146 硬币翻转