题目大意
一个 n×m 的网格图,其中有的格子有障碍,有的没有。
有 T 个询问,每次询问一个子矩形(x1,y1)−(x2,y2)。查询该子矩形内边长最大的格点正方形边长为多少。一个正方形不能包括有障碍的格子。
1≤n,m≤103,T≤106
题目分析
预处理每隔格子作为左上角能做的最大正方形边长。
一个很显然的想法(和[TJOI&HEOI2016]str/[JZOJ4614]字符串的想法类似):二分边长,转化为判定性问题,查询一个子矩形的最大值是否大于等于二分值。
这里 T 达到了106规模,显然我们需要一个查询 O(1) 的二维 RMQ 算法。二维的 ST 表可以胜任这一工作。
二维的 ST 表预处理实际上和一维是差不多的。在其中一维指数为 0 时转化为一维问题,否则直接让其中任意一个维一分为二即可。
查询类似一维情况,分成四个子矩形即可。
时间复杂度O(nmlog2nlog2m+Tlog2n),卡卡常就过了。
代码实现
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
using namespace std;
typedef pair<int,int> P;
#define ft first
#define sd second
#define mkp(a,b) make_pair(a,b)
inline int read()
{
int x=,f=;
char ch=getchar();
while (!isdigit(ch)) f=ch=='-'?-:f,ch=getchar();
while (isdigit(ch)) x=x*+ch-'0',ch=getchar();
return x*f;
}
int buf[];
inline void write(int x)
{
if (x<) putchar('-'),x=-x;
buf[]=;
while (x) buf[++buf[]]=x%,x/=;
if (!buf[]) buf[]=,buf[]=;
while (buf[]) putchar('0'+buf[buf[]--]);
}
const int N=;
const int LGN=;
int down[N][N],Right[N][N],dwl[N][N],rgl[N][N];
int n,m,T,lgn,head,tail;
int f[LGN][LGN][N][N];
bool a[N][N];
int pw[LGN];
int LOG[N];
P que[N];
void add(P x)
{
while (head<=tail&&que[tail].ft>=x.ft) tail--;
que[++tail]=x;
}
int getmin(int x)
{
while (head<=tail&&que[head].sd>x) head++;
return que[head].ft;
}
void pre()
{
for (int i=;i<=n;i++)
for (int j=m;j>=;j--)
Right[i][j]=a[i][j]?Right[i][j+]+:;
for (int j=;j<=m;j++)
for (int i=n;i>=;i--)
down[i][j]=a[i][j]?down[i+][j]+:;
for (int i=;i<=n;i++)
{
head=,tail=;
for (int cur=m,j=m;j>=;j--)
{
add(mkp(down[i][j],j));
while (cur>=j&&getmin(cur)<cur-j+) cur--;
rgl[i][j]=cur;
}
}
for (int j=;j<=m;j++)
{
head=,tail=;
for (int cur=n,i=n;i>=;i--)
{
add(mkp(Right[i][j],i));
while (cur>=i&&getmin(cur)<cur-i+) cur--;
dwl[i][j]=cur;
}
}
lgn=trunc(log(n)/log());
pw[]=;
for (int i=;i<=lgn;i++) pw[i]=pw[i-]<<;
for (int i=;i<=n;i++) LOG[i]=trunc(log(i)/log());
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
f[][][i][j]=min(rgl[i][j]-j+,dwl[i][j]-i+);
for (int k=;k<=lgn;k++)
for (int l=;l<=lgn;l++)
if (k||l)
for (int i=;i+pw[k]-<=n;i++)
for (int j=;j+pw[l]-<=m;j++)
if (!k) f[k][l][i][j]=max(f[k][l-][i][j],f[k][l-][i][j+pw[l-]]);
else if (!l) f[k][l][i][j]=max(f[k-][l][i][j],f[k-][l][i+pw[k-]][j]);
else f[k][l][i][j]=max(f[k][l-][i][j],f[k][l-][i][j+pw[l-]]);
}
int query(int x1,int y1,int x2,int y2)
{
int lg1=LOG[x2-x1+],lg2=LOG[y2-y1+];
return max(max(f[lg1][lg2][x1][y1],f[lg1][lg2][x2-pw[lg1]+][y2-pw[lg2]+]),max(f[lg1][lg2][x2-pw[lg1]+][y1],f[lg1][lg2][x1][y2-pw[lg2]+]));
}
int solve(int x1,int y1,int x2,int y2)
{
int l=,r=min(x2-x1+,y2-y1+),mid,ret=;
while (l<=r)
{
mid=l+r>>;
if (query(x1,y1,x2-mid+,y2-mid+)>=mid) l=(ret=mid)+;
else r=mid-;
}
return ret;
}
int main()
{
freopen("square.in","r",stdin),freopen("square.out","w",stdout);
n=read(),m=read();
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
a[i][j]=read();
pre();
for (T=read();T--;)
{
int x1=read(),y1=read(),x2=read(),y2=read();
write(solve(x1,y1,x2,y2)),putchar('\n');
}
fclose(stdin),fclose(stdout);
return ;
}