POJ 3264 Balanced Lineup 最基本的RMQ

其实这个题早就过了，只是当时为了偷懒拿线段树做的。当时肤浅的认为RMQ问题线段树都能胜任，现在才发现毕竟土洋。

不过线段树做多了，RMQ就显得很容易理解了。

其实RMQ很多算法，不过最通用的应属ST算法，总体思想就是一个很简单的dp。

以求区间最大值为例，数组dp[ i ][ j ]记录的是区间[ i , i + (1<

也就是说是从第 i 个元素开始，连续的 (1<

不难发现，dp[ i ][ 0 ] == num[ i ] （num为存储输入数据的数组）。

而连续的 (1<

显然 区间[ i , i + (1<

即 dp[ i ][ j ] = max( dp[ i ][ j-1 ] , dp[ i +(1<<(j-1))][j-1] )。

以上即为该算法的主要思路，而在编码实现过程中还是要注意到那个一万年不许变的问题――边界问题。

当 i +(1<<(j-1)) > n (n为数据量)时，dp[ i ][ j ] = dp[ i ][ j-1 ] ，因为此时没有必要分成两段了。

上面为初始化的思路，下面说一下查询的过程。

对于区间[ L , R ]内的最值可以视为[L,s1] , [s1+1,s2],[ s2+1,s3].......[sn+1,R]这一串连续的小区间的最值中较大的一个。

而 si 显然要满足 L <= si <= R,且每一段小区间的长度为 2^j (j为非负整数)。

即：

1. 每次都要找一个尽量大的满足上述要求的 j ，然后查询[L,L+(1<

2. 然后更新L ，L += （1<

3.若L 〉 R，求值过程结束，否则返回第一步。

上面这些即为查询过程。

下面附上AC代码，效率略低唉。。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #pragma comment(linker, "/STACK:1024000000"); #define LL long long int using namespace std; int dpmin[50010][20],dpmax[50010][20]; int num[50010]; int main() { int i,j,m,n,l,r,Max,Min; while(scanf("%d %d",&n,&m) != EOF) { for(i = 1;i <= n; ++i) { scanf("%d",&num[i]); } for(i = 1;i <= n; ++i) { dpmin[i][0] = num[i]; dpmax[i][0] = num[i]; } for(j = 1;(1<<(j-1)) <= n; ++j) { for(i = 1;i <= n; ++i) { if(i+(1<<(j-1)) <= n) { dpmax[i][j] = max(dpmax[i][j-1],dpmax[i+(1<<(j-1))][j-1]); dpmin[i][j] = min(dpmin[i][j-1],dpmin[i+(1<<(j-1))][j-1]); } else { dpmax[i][j] = dpmax[i][j-1]; dpmin[i][j] = dpmin[i][j-1]; } } } while(m--) { scanf("%d %d",&l,&r); Max = num[l],Min = num[l]; while(l <= r) { for(j = 0;l + (1<