「USACO2007JAN」Balanced Lineup

传送门
挖个坑。。。

#include<bits/stdc++.h>
using namespace std;
int n,q,l,r,f1[50002][30],f2[50002][30],a[50002];
void prework(){
    for(int i=1;i<=n;i++){
        f2[i][0]=a[i];
        f1[i][0]=a[i];
    }
    int k=log(n)/log(2);
    for(int j=1;j<=k;j++){
        for(int i=1;i<=n-(1<<j)+1;i++){
            f1[i][j]=max(f1[i][j-1],f1[i+(1<<(j-1))][j-1]);
            f2[i][j]=min(f2[i][j-1],f2[i+(1<<(j-1))][j-1]);
        }
    }
}
int st(int l,int r){
    int k=log(r-l+1)/log(2);
    int x=max(f1[l][k],f1[r-(1<<k)+1][k]);
    int y=min(f2[l][k],f2[r-(1<<k)+1][k]);
    return x-y;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    prework();
    while(q--){
        scanf("%d%d",&l,&r);
        printf("%d\n",st(l,r));
    }
    return 0;
}