题目：点这里
题意：给出一个n*m的矩阵，然后又Q个询问：每个询问有x1,y1,x2,y2，x1,y1为子矩阵的左上角坐标，x2,y2为右上角的坐标。求此子矩阵中元素最大值，判断最大值是否在子矩阵四个角上，在就输出yes，否则输出no。
分析：二维RMQ直接上代码。
#include<iostream> #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; const int max_=301; int dp[max_][max_][9][9];//RMQ的递推数组。1，3维是行，2 4维是列。 int a[max_][max_]; void RMQ_init(int n,int m) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)//初始化 { dp[i][j][0][0]=a[i][j]; } for(int i=0;(1<<i)<=n;i++) for(int j=0;(1<<j)<=m;j++) if(i||j)//i，j不都为0。 { for(int ii=1;ii+(1<<i)-1<=n;ii++) for(int jj=1;jj+(1<<j)-1<=m;jj++) { if(i)//对行递推。 { int k=1<<(i-1); dp[ii][jj][i][j]=max(dp[ii][jj][i-1][j],dp[ii+k][jj][i-1][j]); } else { int k=1<<(j-1); dp[ii][jj][i][j]=max(dp[ii][jj][i][j-1],dp[ii][jj+k][i][j-1]); } } } } int RMQ_Q(int x1,int y1,int x2,int y2)//查询 { int k1=0; while((1<<(k1+1))<=x2-x1+1)k1++; int k2=0; while((1<<(k2+1))<=y2-y1+1)k2++; x2=x2-(1<<k1)+1; y2=y2-(1<<k2)+1; return max(max(dp[x1][y1][k1][k2],dp[x1][y2][k1][k2]),max(dp[x2][y1][k1][k2],dp[x2][y2][k1][k2])); } int main() { int n,m; while(~scanf("%d %d",&n,&m)) { if(!n&&!m) break; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { scanf("%d",&a[i][j]); } RMQ_init(n,m); int k; scanf("%d",&k); while(k--) { int x1,y1,x2,y2; scanf("%d %d %d %d",&x1,&y1,&x2,&y2); int temp=RMQ_Q(x1,y1,x2,y2); printf("%d ",temp); if(temp==a[x1][y1]||temp==a[x1][y2]||temp==a[x2][y1]||temp==a[x2][y2]) printf("yes "); else printf("no "); } } }