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