1 #include<cstdio> 2 #include<cstring> 3 using namespace std; 4 const int N=50001,M=30; 5 int n,q,h[N],minl[N][M],maxl[N][M]; 6 int RMQ(int,int),min(int,int),max(int,int); 7 int main(){ 8     int l,r,tmp; 9     scanf("%d %d",&n,&q);10     for (int i=1;i<=n;i++){11         scanf("%d",&tmp);12         minl[i][0]=maxl[i][0]=tmp;13     }14     for (int j=1;(1<<j)<=n;j++)15         for (int i=1;i+j-1<=n;i++){16             minl[i][j]=min(minl[i][j-1],minl[i+(1<<(j-1))][j-1]);17             maxl[i][j]=max(maxl[i][j-1],maxl[i+(1<<(j-1))][j-1]);18         }19     for (int i=1;i<=q;i++){20         scanf("%d %d",&l,&r);21         printf("%d\n",RMQ(l,r));22     }23     return 0;24 }25 int min(int x,int y){26     return x<y?x:y;27 }28 int max(int x,int y){29     return x>y?x:y;30 }31 int RMQ(int l,int r){32     int k=0;33     while ((1<<(k+1)) <=r-l+1) k++;34     return max(maxl[l][k],maxl[r-(1<<k)+1][k])-min(minl[l][k],minl[r-(1<<k)+1][k]);35 }