[POJ3264]Balanced Lineup

[POJ3264]Balanced Lineup

题意

给一个数列,求数列中$l,r$范围内最大值和最小值的差。

题解

st表模板题。求两次rmq即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstring>
#include<stdio.h>
#include<algorithm>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 5e4 + 10;
int n,q;
int st[maxn][32-__builtin_clz(maxn)];
int st2[maxn][32-__builtin_clz(maxn)];
int h[maxn];
int ST(){
int l = 31 - __builtin_clz(n);
rep(i,0,n) {st[i][0] = h[i];st2[i][0] = h[i];}
rep(j,0,l) rep(i,0,n-(1<<j)+1){
st[i][j+1] = max(st[i][j],st[i+(1<<j)][j]);
st2[i][j+1] = min(st2[i][j],st2[i+(1<<j)][j]);
}
}
int max_rmq(int l,int r){
int k = 31 - __builtin_clz(r-l+1);
return max(st[l][k],st[r-(1<<k)+1][k]);
}
int min_rmq(int l,int r){
int k = 31 - __builtin_clz(r-l+1);
return min(st2[l][k],st2[r-(1<<k)+1][k]);
}
int main(){
#ifdef LOCAL
freopen("shui.in","r",stdin);
#endif
while(~scanf("%d%d",&n,&q)){
rep(i,0,n) scanf("%d",&h[i]);
ST();
while(q--){
int l,r;scanf("%d%d",&l,&r);
l--,r--;
printf("%d\n",max_rmq(l,r)-min_rmq(l,r));
}
}
return 0;
}