题解(二分板子)

没有整体二分题解，写一发。

首先计算出以每个位置 (x,y) 为左上角最大正方形 $f x,y$。

考虑查询，不难发现可以二分。然而对于每个 i 预处理 $f x,y ​ ≥i$ 的前缀和空间开不下。于是可以想到询问离线整体二分。

每次枚举 mid 计算 $f x,y ​ ≥mid$ 的前缀和，这样做空间是 $O(nm)$，而时间是 $min(n,m)nm $的。仔细分析可以发现带
$3$
$1$
​
常数，直接做即可通过。

细节很少，基本是个整体二分板子。

#include <bits/stdc++.h>
#pragma GCC optimize(2,3,"Ofast","inline")
#define int long long
#define double long double
using namespace std;
int a[1005][1005],pre[1005][1005],maxe[1005][1005],ans[1000005],mpre[1005][1005],n,m;
struct qry{
	int a1,a2,b1,b2,pos;
}c[1000005];
vector<qry> vc1,vc2;
void solve(int l,int r,int ql,int qr){
	if(l==r){
		for(int i=ql;i<=qr;i++) ans[c[i].pos]=l-1;
		return ;
	}
	int mid=(l+r)>>1;
	for(int i=1;i<=n-mid+1;i++) for(int j=1;j<=m-mid+1;j++) mpre[i][j]=mpre[i-1][j]+mpre[i][j-1]-mpre[i-1][j-1]+(maxe[i][j]>=mid);
	for(int i=ql;i<=qr;i++){
		int a3=c[i].a2-mid+1,b3=c[i].b2-mid+1;
		if(b3<c[i].b1||a3<c[i].a1) vc1.push_back(c[i]);
		else if(mpre[a3][b3]-mpre[c[i].a1-1][b3]-mpre[a3][c[i].b1-1]+mpre[c[i].a1-1][c[i].b1-1]>0) vc2.push_back(c[i]);
		else vc1.push_back(c[i]);
	}
//	cout<<l<<" "<<r<<" "; 
	int it=ql;
	for(auto v:vc1) c[it++]=v;
	int md=it-1;
	for(auto v:vc2) c[it++]=v;
	vc1.clear(),vc2.clear();
//	cout<<md<<"\n";
	solve(l,mid,ql,md);
	solve(mid+1,r,md+1,qr);
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]),pre[i][j]=pre[i-1][j]+pre[i][j-1]-pre[i-1][j-1]+a[i][j];
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){
		int l=0,r=min(n-i+1,m-j+1);
		while(l<r){
			int mid=(l+r+1)>>1;
			if(pre[i+mid-1][j+mid-1]-pre[i-1][j+mid-1]-pre[i+mid-1][j-1]+pre[i-1][j-1]==mid*mid) l=mid;
			else r=mid-1;
		} 
		maxe[i][j]=l;
//		cout<<l<<" ";
	} 
	int q; scanf("%lld",&q);
	for(int i=1;i<=q;i++) scanf("%lld%lld%lld%lld",&c[i].a1,&c[i].b1,&c[i].a2,&c[i].b2),c[i].pos=i;
	solve(0,min(n,m)+1,1,q);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}