第三题的： #include<bits/stdc++.h> using namespace std; const int N=1e5+5,M=20; int n,m; int a[N]; int maxf[N][M]; int minf[N][M]; int querymax(int l,int r) { int len=r-l+1; int k=(log(len)/log(2)); return max(maxf[l][k],maxf[r-(1<<k)+1][k]); } int querymin(int l,int r) { int len=r-l+1; int k=(log(len)/log(2)); return min(minf[l][k],minf[r-(1<<k)+1][k]); } int main() { cin>>n>>m; for(int i=1;i<=n;i++) cin>>a[i]; for(int j=0;j<M;j++){ for(int i=1;i+(1<<j)-1<=n;i++) { if(j==0) maxf[i][j]=a[i]; else{ maxf[i][j]=max(maxf[i][j-1],maxf[i+(1<<(j-1))][j-1]); } } } for(int j=0;j<M;j++){ for(int i=1;i+(1<<j)-1<=n;i++) { if(j==0) minf[i][j]=a[i]; else{ minf[i][j]=min(minf[i][j-1],minf[i+(1<<(j-1))][j-1]); } } } while(m--){ int x,y;cin>>x>>y; cout<<querymax(x,y)-querymin(x,y)<<endl; } return 0; }