[POJ3264]Balanced Lineup

题意

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

题解

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

#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;
}