Balanced Lineup

题意：
给一个数组，每次询问一个区间，输出区间内最大值和最小值的差。

思路：维护一个区间最小值，一个区间最大值

Code：

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn=50007;
inline ll read() {
    ll s = 0, w = 1;
    char ch = getchar();
    while (ch < 48 || ch > 57) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= 48 && ch <= 57)
        s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
int mx[maxn<<2],mn[maxn<<2];
inline void build(int l,int r,int rt) {
    if(l==r) {
        mx[rt]=mn[rt]=read();
        return;
    }
    int mid=l+r>>1;
    build(l,mid,rt<<1);
    build(mid+1,r,rt<<1|1);
    mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
inline int query(int x,int y,int l,int r,int rt) {
    if(x<=l&&r<=y) return mx[rt];
    int mid=l+r>>1,a=0,b=0;
    if(x<=mid) a=query(x,y,l,mid,rt<<1);
    if(y>mid) b=query(x,y,mid+1,r,rt<<1|1);
    return max(a,b);
}
inline int query2(int x,int y,int l,int r,int rt) {
    if(x<=l&&r<=y) return mn[rt];
    int mid=l+r>>1,a=0x3f3f3f3f,b=0x3f3f3f3f;
    if(x<=mid) a=query2(x,y,l,mid,rt<<1);
    if(y>mid) b=query2(x,y,mid+1,r,rt<<1|1);
    return min(a,b);
}
int main() {
    int n=read(),q=read(),x,y;
    build(1,n,1);
    while(q--) {
        x=read(),y=read();
        printf("%d\n",query(x,y,1,n,1)-query2(x,y,1,n,1));
    }
    return 0;
}