Codeforces713D（二维RMQ）

区间最大子正方形问题。
预处理后二分答案验证

AC Code：

#include<bits/stdc++.h>
#define maxn 1005
#define lim 10
using namespace std;int n,m,dp[maxn][maxn],s[maxn][maxn],f[10][10][maxn][maxn],lg[1<<10];
inline int Query(int a,int b,int c,int d)
{if(a>c || b>d) return 0;int l1 = lg[c - a + 1]  ,l2=lg[d - b + 1];return max(max(f[l1][l2][a][b],f[l1][l2][c-(1<<l1)+1][b]),max(f[l1][l2][a][d-(1<<l2)+1],f[l1][l2][c-(1<<l1)+1][d-(1<<l2)+1]));
}int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&s[i][j]);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(s[i][j])if(i==1 || j==1) dp[i][j] = 1;else dp[i][j] = min(dp[i-1][j],min(dp[i][j-1],dp[i-1][j-1]))+1;for(int a=0;a<lim;a++)for(int b=0;b<lim;b++)for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(a==0 && b==0) f[a][b][i][j] = dp[i][j];else if(a==0){int v = j + (1<<b-1);f[a][b][i][j] = max(f[a][b-1][i][j],f[a][b-1][i][v]);}else if(b==0){int u = i + (1<<a-1);f[a][b][i][j] = max(f[a-1][b][i][j],f[a-1][b][u][j]);}else {int u = i + (1<<a-1) , v = j + (1<<b-1);f[a][b][i][j] = max(max(f[a-1][b-1][i][j],f[a-1][b-1][u][j]) , max(f[a-1][b-1][i][v],f[a-1][b-1][u][v]));}}for(int i=2;i<maxn;i++) lg[i] = lg[i>>1] + 1;int q,a,b,c,d;for(scanf("%d",&q);q--;){scanf("%d%d%d%d",&a,&b,&c,&d);int L = 0 , R = min(c-a+1,d-b+1) , mid;for(;L<R;){	mid = (L+R+1) >> 1;if(Query(a+mid-1,b+mid-1,c,d) >= mid) L = mid;else R = mid - 1;}printf("%d\n",L);}
}