Animals and Puzzle 题解

原题链接：CF713D

题意：给定一个 \(n\times m\) 的地图 \(a\)，\(a_{i}\) 为 \(0\) 或 \(1\)。有 \(t\) 次询问，每次询问给定一个矩形，求出这个矩形中最大的由 \(1\) 构成的正方形的边长是多少。

首先考虑预处理出 \(d_{i,j}\) 表示以 \((i,j)\) 为左上角的最大正方形边长是多少。

对于每一次询问可以二分一个 \(mid\)，判断 \(mid\) 是否可行就相当于是查询 \(d\) 的一个二维区间中的最大值，如果这个最大值大于等于 \(mid\) 说明可行，否则不可行，注意如果这个二维区间的长宽的最小值比 \(mid\) 小的话，那么肯定不可行。而二维区间 \(\max\) 直接用二维 ST 表维护即可，时间复杂度 \(O(n^{2} \log ^{2}n+t \log n)\)。

预处理 \(d\) 数组可以用 \(O(n^{2} \log n)\) 的二分或者 \(O(n^{2})\) 的 dp。

#include<bits/stdc++.h>
/* --------------- fast io --------------- */ // begin
namespace Fread {
const int SIZE = 1 << 21;
char buf[SIZE], *S, *T;
inline char getchar() {
	if (S == T) {
		T = (S = buf) + fread(buf, 1, SIZE, stdin);
		if (S == T) return '\n';
	}
	return *S++;
}
} // namespace Fread
namespace Fwrite {
const int SIZE = 1 << 21;
char buf[SIZE], *S = buf, *T = buf + SIZE;
inline void flush() {
	fwrite(buf, 1, S - buf, stdout);
	S = buf;
}
inline void putchar(char c) {
	*S++ = c;
	if (S == T) flush();
}
struct NTR {
	~ NTR() { flush(); }
} ztr;
} // namespace Fwrite
#ifdef ONLINE_JUDGE
#define getchar Fread :: getchar
#define putchar Fwrite :: putchar
#endif
namespace Fastio {
struct Reader {
	template<typename T>
	Reader& operator >> (T& x) {
		char c = getchar();
		T f = 1;
		while (c < '0' || c > '9') {
			if (c == '-') f = -1;
			c = getchar();
		}
		x = 0;
		while (c >= '0' && c <= '9') {
			x = x * 10 + (c - '0');
			c = getchar();
		}
		x *= f;
		return *this;
	}
	Reader& operator >> (char& c) {
		c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		return *this;
	}
	Reader& operator >> (char* str) {
		int len = 0;
		char c = getchar();
		while (c == ' ' || c == '\n') c = getchar();
		while (c != ' ' && c != '\n' && c != '\r') { // \r\n in windows
			str[len++] = c;
			c = getchar();
		}
		str[len] = '\0';
		return *this;
	}
	Reader(){}
} cin;
const char endl = '\n';
struct Writer {
	template<typename T>
	Writer& operator << (T x) {
		if (x == 0) { putchar('0'); return *this; }
		if (x < 0) { putchar('-'); x = -x; }
		static int sta[45];
		int top = 0;
		while (x) { sta[++top] = x % 10; x /= 10; }
		while (top) { putchar(sta[top] + '0'); --top; }
		return *this;
	}
	Writer& operator << (char c) {
		putchar(c);
		return *this;
	}
	Writer& operator << (char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer& operator << (const char* str) {
		int cur = 0;
		while (str[cur]) putchar(str[cur++]);
		return *this;
	}
	Writer(){}
} cout;
} // namespace Fastio
#define cin Fastio :: cin
#define cout Fastio :: cout
#define endl Fastio :: endl
/* --------------- fast io --------------- */ // end
using namespace std;
#define re register
const int MAXN = 1e3 + 1;
int n,m,sum[MAXN][MAXN],t,x,y,p,q;
bool a[MAXN][MAXN];
short d[MAXN][MAXN],st[MAXN][MAXN][11][11];
inline bool check(int X,int Y,int len)
{
	re int P = X + len - 1,Q = Y + len - 1;
	if(sum[P][Q] - sum[P][Y - 1] - sum[X - 1][Q] + sum[X - 1][Y - 1] == len * len) return true;
	else return false;
}
inline bool solve(int mid)
{
	re int P = p - mid + 1,Q = q - mid + 1;//(x,y),(P,Q)
	int f = __lg(P - x + 1),l = __lg(Q - y + 1);
	if(P < x || Q < y) return false;
	int mx = max(max(st[x][y][f][l],st[P - (1 << f) + 1][y][f][l]),max(st[x][Q - (1 << l) + 1][f][l],st[P - (1 << f) + 1][Q - (1 << l) + 1][f][l]));
//	cout << "x = " << x << " y = " << y << " P = " << P << " Q = " << Q << " " << "max = " << mx << " mid = " << mid<<" f = " << f << " l = " << l << endl;
	if(mx >= mid) return true;
	else return false;
}
signed main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin >> a[i][j];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
	for(int i = 1;i <= n;i++)
		for(int j = 1;j <= m;j++)
		{
			re int l = 1,r = min(n - i + 1,m - j + 1);
			while(l <= r)
			{
				int mid = (l + r) >> 1;
				if(check(i,j,mid)) d[i][j] = mid,l = mid + 1;
				else r = mid - 1;
			}
			st[i][j][0][0] = d[i][j];
		}
	for(int i = 0;i <= __lg(n) + 1;i++)
		for(int j = 0;j <= __lg(m) + 1;j++)
		{
			if(i == 0 && j == 0) continue;
			for(int s = 1;s <= (n - (1 << i) + 1);s++)
				for(int e = 1;e <= (m - (1 << j) + 1);e++)
				{
//					if(s + (1 << i) > n || e + (1 << j) > m) continue;
					if(i != 0) st[s][e][i][j] = max(st[s][e][i - 1][j],st[s + (1 << i - 1)][e][i - 1][j]);
					else st[s][e][i][j] = max(st[s][e][i][j - 1],st[s][e + (1 << j - 1)][i][j - 1]);
//					cout << s << " " << e << " " << s + (1 << i) - 1 << " " << e + (1 << j) - 1 << " " << st[s][e][i][j] << endl;
				}
		}
	cin >> t;
	while(t--)
	{
		cin >> x >> y >> p >> q;
		int l = 0,r = max(n,m),ans = 0;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			if(solve(mid) == true) ans = mid,l = mid + 1;
			else r = mid - 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}
/*
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4
*/