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
",qmax(x,y)-qmin(x,y));
52     }
53     return 0;
54 }