二维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][9][9]; void ST(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) dpmax[i][j][0][0]=val[i][j]; int k1=log2(n),k2=log2(m); for(int i=0;i<=k1;i++)//横向 for(int j=0;j<=k2;j++){//纵向 if(i==0 && j==0) continue; for(int r=1;r+(1<<i)-1<=n;r++) for(int c=1;c+(1<<j)-1<=m;c++) if(i==0) dpmax[r][c][i][j]=max(dpmax[r][c][i][j-1],dpmax[r][c+(1<<(j-1))][i][j-1]); else dpmax[r][c][i][j]=max(dpmax[r][c][i-1][j],dpmax[r+(1<<(i-1))][c][i-1][j]); } } int query(int r1,int c1,int r2,int c2){ int kr=log2(r2-r1+1),kc=log2(c2-c1+1); int t1=dpmax[r1][c1][kr][kc]; int t2=dpmax[r2-(1<<kr)+1][c1][kr][kc]; int t3=dpmax[r1][c2-(1<<kc)+1][kr][kc]; int t4=dpmax[r2-(1<<kr)+1][c2-(1<<kc)+1][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)==2){ for(int i=1;i<=n;i++) for(int j=1;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 0; }