st.cpp

来自「RMQ问题。。 不用线段树实现。 ST算法运用的是动态规划和二进制优化的思想。」· C++ 代码 · 共 46 行

/*
  Date: 27/07/08 14:52
  Description: RMQ--ST算法 
*/
#include    <iostream>
#include    <cmath>
#define  max(a , b) (a > b ? a : b)
#define  min(a , b) (a < b ? a : b)
const    int     MaxN = 10000 + 1;
int      f[MaxN][33] , N , a[MaxN];
void     Input()
{
         freopen("input.txt","r",stdin);
         freopen("output.txt","w",stdout);
         scanf("%d",&N);
         int  i;
         for (i = 1 ; i <= N ; i++)
             scanf("%d" , &a[i]);          
}
void     Pre()
{
         int  i , k , j;
         for (i = 1 ; i <= N ; i++)
             f[i][0] = a[i];
         k = int (log( (double) N )/ log(2.0));
         for (j = 1 ; j <= k ; j++)
            for (i = 1 ; i <=N - (1<<(j - 1)) ; i++)
               f[i][j] = max(f[i][j-1] , f[i + (1 << (j - 1))][j-1]) ;                
}
void     RMQ()
{
         int l ,  r  , k;
         while (scanf("%d%d",&l,&r) == 2)
         {
                 k = int( log( double (r-l+1))/ log(2.0) );
                 printf("%d\n",max(f[l][k] , f[ r - (1 << k) + 1][k]));     
         }         
}
int      main()
{
         Input();
         Pre();
         RMQ();
         return  0;
}