Description

有n头牛排成一个数列，给q个询问，每个询问给定l和r，求[l,r]区间内最高的牛和最低的牛的身高差。

Sample Input

6 3

1

7

3

4

2

5

1 5

4 6

2 2

Sample Output

6

3

0

题解：

　　下午依然很水……

　　RMQ问题，这次用st表来解决，直接上板子就好，最大最小各求一下，相减即得。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 const int maxn=50009; 7 int st_max[maxn][20],st_min[maxn][20]; 8 int n,q,a[maxn],l,r; 9 void init_st()10 {11     for(int i=n;i>=1;i--)12     {13         st_max[i][0]=a[i];14         st_min[i][0]=a[i];15         for(int j=1;(i+(1<
          
           <=n;j++)16         {17             st_max[i][j]=max(st_max[i][j-1],st_max[i+(1<