原题链接：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
*/