Description
Analysis
我們可以想到一個DP，f[i][j]表示(i,j)為右下角的最大正方形邊長。
則 f[i][j]=Min(f[i−1][j−1],f[i−1][j],f[i][j−1])+1
那麼可以二分答案，在合法範圍内找是否有f[x][y]>=mid。
時間複雜度 O(Tn2logn) ，逾時。
注意到f是靜态的，有什麼東西可以靜态查詢區間最大值？
沒錯，就是RMQ，不過是二維的。
其實二維rmq也差不多，設rmq[k][l][i][j]表示以(i,j)為右下角，向上2^i個格子，向左2^j個格子的矩形内f的最大值。那麼預處理rmq數組就是 O(n2log2n)
對于二分出來的數，有了rmq數組我們就可以O(1)判斷，是以時間複雜度為 O(Tlogn)
Code
#include<cstdio>
#include<cmath>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int N=;
int n,m,_2[],f[N][N],rmq[11][][N][N];
bool map[N][N];
char ch;
int read()
{
int t=,p=;
for(ch=getchar();ch<'0' || ch>'9';ch=getchar())
if(ch=='-') p=-;
for(;'0'<=ch && ch<='9';ch=getchar()) t=t*10+ch-'0';
return t*p;
}
int query(int x1,int y1,int x2,int y2)
{
if(x1>x2 || y1>y2) return ;
int l1=log2(x2-x1+),l2=log2(y2-y1+);
int ans=max(rmq[l1][l2][x2][y2],rmq[l1][l2][x2][y1+_2[l2]-]);
ans=max(ans,max(rmq[l1][l2][x1+_2[l1]-][y2],rmq[l1][l2][x1+_2[l1]-][y1+_2[l2]-]));
return ans;
}
bool check(int x1,int y1,int x2,int y2,int l)
{
return query(x1+l-,y1+l-,x2,y2)>=l;
}
int main()
{
freopen("square.in","r",stdin);
freopen("square.out","w",stdout);
_2[]=;
fo(i,,) _2[i]=_2[i-]*2;
int ,x1,y1,x2,y2;
n=read(),m=read();
fo(i,,n)
fo(j,,m)
{
map[i][j]=read();
if(map[i][j]) f[i][j]=min(min(f[i-][j],f[i][j-]),f[i-][j-])+;
rmq[0][][i][j]=f[i][j];
}
fo(k,,log2(n))
fo(i,,n)
fo(j,,m)
{
rmq[0][k][i][j]=max(rmq[0][k-][i][j],rmq[0][k-][i][j-_2[k-]]);
rmq[k][][i][j]=max(rmq[k-1][][i][j],rmq[k-1][][i-_2[k-]][j]);
}
fo(k,,log2(n))
fo(l,,log2(m))
fo(i,_2[k],n)
fo(j,_2[l],m)
rmq[k][l][i][j]=max(rmq[k][l-][i][j],rmq[k][l-][i][j-_2[l-]]);
=read();
while(--)
{
x1=read(),y1=read(),x2=read(),y2=read();
int l=,r=min(y2-y1+,x2-x1+);
while(l+<r)
{
int mid=(l+r)>>;
if(check(x1,y1,x2,y2,mid)) l=mid;
else r=mid-;
}
while(check(x1,y1,x2,y2,l+)) l++;
printf("%d\n",l);
}
return ;
}