题目大意：给你一个(n*m)的矩阵，矩阵上有一些点是障碍，有(T)次询问，每次给你一个矩形(x1,y1,x2,y2)，你要在这个矩形内找一个最大正方形使得正方形内不包含障碍。
(n,mleq 1000,T leq 10^6)
Solution
假设没有给定矩形的限制，设(f[i][j])表示以((i,j))为右下角最大不包含障碍的正方形，转移如下：
- ((i,j))有障碍则(f[i][j]=0)
- ((i,j))无障碍则(f[i][j]=min(f[i-1][j],f[i][j-1],f[i-1][j-1])+1)
现在有了矩形的限制，我们可以二分答案(mid)，则若矩形((x1+mid-1,y1+mid-1))到((x2,y2))中(f)的最大值大于等于(mid)，这个(mid)就是合法的了。查询范围的左上角((x1+mid-1,y1+mid-1))相当于保证了最大的正方形不超出矩形范围。
于是用一个二维rmq维护矩阵最大值即可，时空复杂度均为(O(n^2log^2n))。
Tips: 由于没有按题解说的开mx[10][10][N][N]而开了mx[N][N][10][10]，导致程序TLE。这说明多维数组把小的下标开在前面可以显著提高访问速度，涨知识了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
using namespace std;
const int N=1007;
inline int read(){
int x=0,f=0;
char c=getchar();
for(;c<'0'||c>'9';c=getchar())if(c=='-')f=1;
for(;c>='0'&&c<='9';c=getchar())x=(x<<1)+(x<<3)+(c^'0');
return f?-x:x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
int n,m,T,a[N][N],f[N][N],mx[10][10][N][N],Log[N],two[10];
int x1,y1,x2,y2,l,r,mid,ans;
inline int qrymax(int x1,int y1,int x2,int y2){
int k=Log[x2-x1+1],l=Log[y2-y1+1];
return max(max(mx[k][l][x1][y1],mx[k][l][x2-two[k]+1][y2-two[l]+1]),max(mx[k][l][x1][y2-two[l]+1],mx[k][l][x2-two[k]+1][y1]));
}
int main(){
//freopen("in","r",stdin);
//freopen("square.in","r",stdin);
//freopen("square.out","w",stdout);
Log[1]=0;for(int i=2;i<=1000;++i)Log[i]=Log[i>>1]+1;
for(int i=0;i<=9;++i)two[i]=(1<<i);
n=read(),m=read();
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j)a[i][j]=read();
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j){
if(a[i][j])f[i][j]=min(f[i-1][j-1],min(f[i-1][j],f[i][j-1]))+1;
else f[i][j]=0;
}
for(rg int i=1;i<=n;++i)for(rg int j=1;j<=m;++j)mx[0][0][i][j]=f[i][j];
for(rg int k=0;k<=Log[n];++k)for(rg int l=0;l<=Log[m];++l){
if(k+l==0)continue;
for(rg int i=1;i+two[k]-1<=n;++i)for(rg int j=1;j+two[l]-1<=m;++j){
if(l==0)mx[k][l][i][j]=max(mx[k-1][l][i][j],mx[k-1][l][i+two[k-1]][j]);
else mx[k][l][i][j]=max(mx[k][l-1][i][j],mx[k][l-1][i][j+two[l-1]]);
}
}
T=read();
while(T--){
x1=read(),y1=read(),x2=read(),y2=read();
l=1,r=min(x2-x1+1,y2-y1+1),ans=0;
while(l<=r){
mid=l+r>>1;
if(qrymax(x1+mid-1,y1+mid-1,x2,y2)>=mid)ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d
",ans);
}
return 0;
}