题解 | 算法竞赛进阶指南-Balanced Lineup

给定一个序列，每次询问一个区间的极差。

其实就是RMQ最大值和最小值一减即可

维护最值显然有ST表(O(nlogn)-O(1))，线段树(O(n)-O(logn))，笛卡尔树(O(n)-O(1))等等多种方法。

我们维护一个线段树，每个节点维护对应区间的最大值和最小值，询问循规蹈矩询问即可。

#include<bits/stdc++.h>

#define ls (rt<<1)
#define rs (rt<<1|1)

using namespace std;

const int INF=(1<<30);
const int maxn=114514*4;

inline int read() {
    int res=0,fh=1;
    char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}

int mn[maxn],mx[maxn],a[maxn];
int n,m;

inline int Min(int a,int b){return a<b?a:b;}
inline int Max(int a,int b){return a>b?a:b;}

inline void pushup(int rt){
    mn[rt]=Min(mn[ls],mn[rs]);
    mx[rt]=Max(mx[ls],mx[rs]);
}

inline void build(int rt,int l,int r){
    if(l==r){
        mx[rt]=mn[rt]=a[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);build(rs,mid+1,r);
    pushup(rt);
}

inline int quemn(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r) return mn[rt];
    int mid=(l+r)>>1;
    int res=INF;
    if(ql<=mid) res=Min(res,quemn(ls,l,mid,ql,qr));
    if(qr>mid)  res=Min(res,quemn(rs,mid+1,r,ql,qr));
    return res;
}

inline int quemx(int rt,int l,int r,int ql,int qr){
    if(ql<=l&&qr>=r) return mx[rt];
    int mid=(l+r)>>1;
    int res=-INF;
    if(ql<=mid) res=Max(res,quemx(ls,l,mid,ql,qr));
    if(qr>mid)  res=Max(res,quemx(rs,mid+1,r,ql,qr));
    return res;
}

int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    build(1,1,n);
    while(m--){
        int l=read(),r=read();
        printf("%d\n",quemx(1,1,n,l,r)-quemn(1,1,n,l,r));
    }
}