posts - 218, comments - 61, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

RMQ(Range Minimum/Maximum Query) 实现

Posted on 2007-08-30 00:49 魔のkyo 阅读(1051) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

 

//RMQ(Range Minimum/Maximum Query)  example:pku3368
//预处理O(nlogn) 查询O(1)
//下标从0开始
const int MAXN=100000+1;
const int MAXF=17;
const int INF=0x7FFFFFFF;
//可以断言 ceiil(log(MAXN,2))==MAXF

inline 
int max(int a,int b){return a>b?a:b;} 

class{
    
int dp[MAXN][MAXF+1];//dp[i][j]表示从a[i]起连续2^j次方个数的最大值
public:
    
void init(int* a,int n){
        
for(int i=0;i<n;i++){
            dp[i][
0]=a[i];
        }
        
for(int f=1,s=1;s<n;s=(1<<f++)){
            
for(int i=0;i+s<n;i++){
                dp[i][f]
=max(dp[i][f-1],dp[i+s][f-1]);
            }            
        }
    }
    
    
int query(int l,int r){
        
if(l>r)return -INF;
        
int d=r-l+1;
        
int f;
        
for(f=0;(1<<f)<=d;f++);
        f
--;
        
return max(dp[l][f],dp[r-(1<<f)+1][f]);
    }
}RMQ;
只有注册用户登录后才能发表评论。