解题关键：rmq模板题，可以用st表，亦可用线段树等数据结构
log10和log2都可，这里用到了对数的换底公式
类似于区间dp，用到了倍增的思想
$F[i][j] = min (F[i][j - 1],F[i + 1 < < (j - 1)][j - 1])$
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<cmath> 6 #include<iostream> 7 using namespace std; 8 typedef long long ll; 9 int a[50002]; 10 int lg; 11 int min1[50002][22],max1[50002][22],n,q; 12 void rmq(int n){ 13 for(int j=1;j<=lg;j++){ 14 for(int i=1;i+(1<<j)-1<=n;i++){ 15 max1[i][j]=max(max1[i][j-1],max1[i+(1<<(j-1))][j-1]); 16 min1[i][j]=min(min1[i][j-1],min1[i+(1<<(j-1))][j-1]); 17 } 18 } 19 } 20 int main(){ 21 int n,q; 22 ios::sync_with_stdio(0); 23 cin.tie(0); 24 cout.tie(0); 25 cin>>n>>q; 26 lg=int(log10(n)/log10(2)); 27 for(int i=1;i<=n;i++) cin>>a[i],min1[i][0]=max1[i][0]=a[i]; 28 rmq(n); 29 while(q--){ 30 int a,b; 31 cin>>a>>b; 32 if(a>b) swap(a,b); 33 int k=(int)(log10(b-a+1)/log10(2.0)); 34 int maxres=max(max1[a][k],max1[b-(1<<k)+1][k]); 35 int minres=min(min1[a][k],min1[b-(1<<k)+1][k]); 36 cout<<maxres-minres<<" "; 37 } 38 }