Posted on 2007-09-22 11:11
魔のkyo 阅读(431)
评论(0) 编辑 收藏 引用 所属分类:
Algorithm
//RMQ-2D example 2859
const int MAXN=300+1;
const int MAXM=300+1;
const int MAXF=9;
const int MAXE=9;
const int INF=0x7FFFFFFF;
inline int max(int a,int b){return a>b?a:b;}
inline int max(int a,int b,int c,int d){return a>?=b>?=c>?=d;}
int a[MAXN][MAXM],n,m;
class{
int dp[MAXN][MAXF+1][MAXM][MAXE+1];//dp[i][f][j][e]表示以(i,j)为左上角元素大小为2^f * 2^e的矩阵中的最大(小)值
public:
void init(){
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
dp[i][0][j][0]=a[i][j];
for(int j=0;j<m;j++)
for(int f=1,s=1;s<n;s=(1<<f++))
for(int i=0;i+s<n;i++)
dp[i][f][j][0]=max(dp[i][f-1][j][0],dp[i+s][f-1][j][0]);
for(int i=0;i<n;i++)
for(int e=1,r=1;r<m;r=(1<<e++))
for(int j=0;j+r<m;j++)
dp[i][0][j][e]=max(dp[i][0][j][e-1],dp[i][0][j+r][e-1]);
for(int f=1,s=1;s<n;s=(1<<f++))
for(int e=1,r=1;r<m;r=(1<<e++))
for(int i=0;i+s<n;i++)
for(int j=0;j+r<m;j++)
dp[i][f][j][e]=max(dp[i][f-1][j][e-1],
dp[i+s][f-1][j][e-1],
dp[i][f-1][j+r][e-1],
dp[i+s][f-1][j+r][e-1]);
}
int query(int x1,int y1,int x2,int y2){
if(x1>x2 || y1>y2)return -INF;
int dx=x2-x1+1;
int dy=y2-y1+1;
int f,e;
for(f=0;(1<<f)<=dx;f++);
for(e=0;(1<<e)<=dy;e++);
f--;e--;
return max(dp[x1][f][y1][e],
dp[x2-(1<<f)+1][f][y1][e],
dp[x1][f][y2-(1<<e)+1][e],
dp[x2-(1<<f)+1][f][y2-(1<<e)+1][e]);
}
}RMQ;