hdu2888 二维ST表(RMQ)

二维RMQ其实和一维差不太多,但是dp时要用四维

/*
二维rmq
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
#define maxn 305
int val[maxn][maxn],n,m;
int dpmax[maxn][maxn][][];
void ST(){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++) dpmax[i][j][][]=val[i][j];
int k1=log2(n),k2=log2(m);
for(int i=;i<=k1;i++)//横向
for(int j=;j<=k2;j++){//纵向
if(i== && j==) continue;
for(int r=;r+(<<i)-<=n;r++)
for(int c=;c+(<<j)-<=m;c++)
if(i==) dpmax[r][c][i][j]=max(dpmax[r][c][i][j-],dpmax[r][c+(<<(j-))][i][j-]);
else dpmax[r][c][i][j]=max(dpmax[r][c][i-][j],dpmax[r+(<<(i-))][c][i-][j]);
}
}
int query(int r1,int c1,int r2,int c2){
int kr=log2(r2-r1+),kc=log2(c2-c1+);
int t1=dpmax[r1][c1][kr][kc];
int t2=dpmax[r2-(<<kr)+][c1][kr][kc];
int t3=dpmax[r1][c2-(<<kc)+][kr][kc];
int t4=dpmax[r2-(<<kr)+][c2-(<<kc)+][kr][kc];
return max(max(t1,t2),max(t3,t4));
}
int main(){
int i,j,q;
int r1,c1,r2,c2;
while(scanf("%d%d",&n,&m)==){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
scanf("%d",&val[i][j]);
ST();
scanf("%d",&q);
while(q--){
scanf("%d%d%d%d",&r1,&c1,&r2,&c2);
int ret=query(r1,c1,r2,c2);
printf("%d ",ret);
if(val[r1][c1]==ret||val[r2][c2]==ret||val[r2][c1]==ret||val[r1][c2]==ret)
puts("yes");
else puts("no");
}
}
return ;
}
上一篇:JQ实战天猫淘宝放大镜


下一篇:Django 模板语言 变量名称