Posted on 2007-08-30 00:49
魔のkyo 阅读(1100)
评论(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;