?

题意：给一串数字，多次询问，求区间最大值和区间最小值的差。

思路：RMQ问题，可以用O(N^2)的预处理，然后每次O(1)的查询，可以用线段树，O(N)的建树，O(logN)的查询，可以用ST表记录，O(NlogN）的预处理，O(1)的查询。

实际上ST表的预处理过程也是一个DP的过程dp[i][j]表示从第i位开始连续2^j位的区间最值。

预处理：dp[i][j]=min(dp[i][j],dp[i+2^j][j]），查询：query(l,r)=min(dp[l][k],dp[r-2^k+1][k])，k保证2^k<=r-l+1且2^(k+1)>=r-l+1。

代码：

?

#include 
  
   
#include 
   
     #include 
    
      #define maxn 50010 using namespace std; int stTable_min[maxn][32],stTable_max[maxn][32]; int preLog2[maxn],aa[maxn]; void st_prepare(int n,int *array) { preLog2[1]=0; for(int i=2; i<=n; i++) { preLog2[i]=preLog2[i-1]; if((1<
     
      =0; i--) { stTable_min[i][0]=array[i]; stTable_max[i][0]=array[i]; for(int j=1; (i+(1<
      
       
?