【题意】给定n*m的01矩阵，Q次询问某个子矩阵内的最大正方形全1子矩阵边长。n,m<=1000，Q<=10^6。
【算法】动态规划DP+二维ST表
【题解】设f[i][j]为以(i,j)为右下角的最大正方形全1子矩阵。
f[i][j]=min{ f[i-1][j-1] , f[i][j-1] , f[i-1][j] }+1
然后用二维ST表处理f[i][j]的子矩阵最小值。
对于每次询问，二分边长x，答案即子矩阵(x1+x-1,y1+x-1)~(x2,y2)的f最小值。
特别注意：若是ST表直接处理二维，需要先预处理[0][1]和[1][0]的情况（即只有一条边的情况）。比较推荐先处理每行后再处理列。
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
using namespace std;
int read(){
char c;int s=,t=;
while(!isdigit(c=getchar()))if(c=='-')t=-;
do{s=s*+c-'';}while(isdigit(c=getchar()));
return s*t;
}
const int maxn=;
int a[maxn][maxn],c[maxn][maxn][][],logs[maxn],n,m;
void ST(){
logs[]=-;for(int i=;i<=max(n,m);i++)logs[i]=logs[i>>]+;
for(int k=;(<<k)<=n;k++)for(int l=;(<<l)<=m;l++)if(k||l)
for(int i=;i+(<<k)-<=n;i++)for(int j=;j+(<<l)-<=m;j++){
if(!k){c[i][j][k][l]=max(c[i][j][k][l-],c[i][j+(<<(l-))][k][l-]);continue;}
if(!l){c[i][j][k][l]=max(c[i][j][k-][l],c[i+(<<(k-))][j][k-][l]);continue;}
int s=max(c[i][j][k-][l],c[i][j][k][l-]);
c[i][j][k][l]=max(c[i+(<<(k-))][j+(<<(l-))][k-][l-],s);
}
}
int query(int x1,int y1,int x2,int y2){
if(x2<x1||y2<y1)return -;
int k=logs[x2-x1+],l=logs[y2-y1+];
int s=max(c[x1][y1][k][l],c[x2-(<<k)+][y2-(<<l)+][k][l]);
int t=max(c[x2-(<<k)+][y1][k][l],c[x1][y2-(<<l)+][k][l]);
return max(s,t);
}
int main(){
n=read();m=read();
for(int i=;i<=n;i++)for(int j=;j<=m;j++){
a[i][j]=read();
if(a[i][j])c[i][j][][]=min(c[i-][j-][][],min(c[i-][j][][],c[i][j-][][]))+;
}
ST();
int T=read();
while(T--){
int x1=read(),y1=read(),x2=read(),y2=read();
int l=,r=min(x2-x1+,y2-y1+)+,mid;
while(l<r){
mid=(l+r)>>;
if(query(x1+mid-,y1+mid-,x2,y2)>=mid)l=mid+;else r=mid;
}
printf("%d\n",l-);
}
return ;
}