1 #include <iostream> 2 #include <cstdio> 3 #include <string.h> 4 #include <cmath> 5 using namespace std; 6 const int N= 50002; 7 int maxn[N][17],minn[N][17]; 8 int a[N]; 9 int n,q;10 void getRMQ(){11     for(int i=1;i<N;i++){maxn[i][0]=minn[i][0]=a[i];}12     for(int j=1;j<17;j++){13         for(int i=1;i<N;i++){14             if(i+(1<<j)<N){15                 maxn[i][j]=max(maxn[i][j-1],maxn[i+(1<<(j-1))][j-1]);16                 minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);17             }  18         }19     }20 }21 int rmq(int l,int r){22     int k=(int)(log((double)(r-l+1))/log(2.0));23     int Max=max(maxn[l][k],maxn[r-(1<<k)+1][k]);24     int Min=min(minn[l][k],minn[r-(1<<k)+1][k]);25     return Max-Min;26 }27 int main(){28     int l,r;29     scanf("%d%d",&n,&q);30     for(int i=1;i<=n;i++){31         scanf("%d",&a[i]);32     }33     getRMQ();34     while(q--){35         scanf("%d%d",&l,&r);36         printf("%d\n",rmq(l,r));37     }38     return 0;39 }