Time Limit: 2000/10000 MS
(Java/Others) Memory Limit: 32768/32768 K
(Java/Others)
Total Submission(s): 1646 Accepted
Submission(s): 597
#include<iostream> #include<cmath> #include<cstdio> using namespace std; const int maxn=301; const int maxm=9; int A[maxn][maxn],flag; int d[maxn][maxn][maxm][maxm]; inline int max(int a,int b){ return a>b?a:b;} void RMQ_init(int n,int m) { int i,j,k,l; for(i=0;i<n;i++) for(j=0;j<m;j++) d[i][j][0][0]=A[i][j]; for(i=0;(1<<i)<=n;i++) { for(j=0;(1<<j)<=m;j++) { if(i==0 && j==0) continue; for(k=0;k+(1<<i)-1<n;k++) { for(l=0;l+(1<<j)-1<m;l++) { if(i==0 && j!=0) d[k][l][i][j]=max(d[k][l][i][j-1],d[k][l+(1<<(j-1))][i][j-1]); else if(i!=0 && j==0) d[k][l][i][j]=max(d[k][l][i-1][j],d[k+(1<<(i-1))][l][i-1][j]); else d[k][l][i][j]=max(d[k][l][i-1][j-1],max(d[k][l+(1<<(j-1))][i-1][j-1], max(d[k+(1<<(i-1))][l][i-1][j-1],d[k+(1<<(i-1))][l+(1<<(j-1))][i-1][j-1]))); } } } } } int query(int lx,int ly,int rx,int ry) { int ri=floor(log(rx-lx+1.0)/log(2.0)+0.000001); int ci=floor(log(ry-ly+1.0)/log(2.0)+0.000001); int temp=d[lx][ly][ri][ci]; temp=max(temp,d[lx][ry-(1<<ci)+1][ri][ci]); temp=max(temp,d[rx-(1<<ri)+1][ly][ri][ci]); temp=max(temp,d[rx-(1<<ri)+1][ry-(1<<ci)+1][ri][ci]); if(temp==A[lx][ly] || temp==A[lx][ry] || temp==A[rx][ly] || temp==A[rx][ry]) flag=1; return temp; } int main() { int n,m,i,j,q,lx,ly,rx,ry,ans; while(~scanf("%d %d",&n,&m)) { for(i=0;i<n;i++) for(j=0;j<m;j++) scanf("%d",&A[i][j]); RMQ_init(n,m); scanf("%d",&q); while(q--) { scanf("%d %d %d %d",&lx,&ly,&rx,&ry); lx--;ly--;rx--,ry--; flag=0; ans=query(lx,ly,rx,ry); printf("%d ",ans); printf(flag?"yes\n":"no\n"); } } return 0; }
原文:http://www.cnblogs.com/xiong-/p/3586546.html