abcdeffa's Blog

当局者迷，旁观者清。

0%

GMOJ S4817 【square】

发表于 更新于

Description

给你一个 $n \times m$ 的只含数字 0 或 1 的矩形，有 $T$ 组询问。

每次询问在以 $(x_1, y_1)$ 为左上角， $(x_2, y_2)$ 为右下角的矩形中全是 1 的正方形的最大边长。

时限三秒，请注意常数因子带来的程序效率上的影响。

Solution

为了方便表述，下文将用 $a_{i, j}$ 来表示矩形中位置为 $(i, j)$ 的数的值。

设 $f_{i, j}$ 表示以 $(i, j)$ 为右下角的正方形的最大边长。

则有转移方程： $f_{i, j} = a_{i, j} \times [min(f_{i - 1, j}, f_{i, j - 1}, f_{i - 1, j - 1}) + 1]$ 。

对于每组询问，可以二分答案。

那么就变成了查询矩阵最大值的问题了。

用 二维 RMQ 即可解决。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <cstdio>
#include <cmath>
#define maxN 1010
#define maxM 1010
int g[11][11][maxN][maxM], f[maxN][maxM], a[maxN][maxM];
int read ()
{
	char c = getchar();
	while(c < '0' || c > '9')
	{
		c = getchar();
	}
	int x = 0;
	while(c >= '0' && c <= '9')
	{
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x;
}
int min (int x, int y)
{
	return x < y ? x : y;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
int query (int xa, int ya, int xb, int yb)
{
	int p = (int)log2(xb - xa + 1), q = (int)log2(yb - ya + 1);
	int ans = max(g[p][q][xa][ya], g[p][q][xb - (1 << p) + 1][ya]);
	ans = max(ans, max(g[p][q][xa][yb - (1 << q) + 1], g[p][q][xb - (1 << p) + 1][yb - (1 << q) + 1]));
	return ans;
}
int main ()
{
	int n = 0, m = 0;
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			f[i][j] = a[i][j] * (min(f[i][j - 1], min(f[i - 1][j - 1], f[i - 1][j])) + 1);
		}
	}
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			g[0][0][i][j] = f[i][j];
		}
	}
	int N = (int)log2(n) + 1, M = (int)log2(m) + 1;
	for(int k = 0;k <= N; k++)
	{
		for(int l = 0;l <= M; l++)
		{
			if(!k && !l)
			{
				continue;
			}
			for(int i = 1;i <= n - (1 << k) + 1; i++)
			{
				for(int j = 1;j <= m - (1 << l) + 1; j++)
				{
					if(k)
					{
						g[k][l][i][j] = max(g[k - 1][l][i][j], g[k - 1][l][i + (1 << (k - 1))][j]);
					}
					else
					{
						g[k][l][i][j] = max(g[k][l - 1][i][j], g[k][l - 1][i][j + (1 << (l - 1))]);
					}
				}
			}
		}
	}
	int T = 0;
	scanf("%d", &T);
	int L = 0, R = min(n, m);
	while(T--)
	{
		int xa = 0, ya = 0, xb = 0, yb = 0;
		xa = read();
		ya = read();
		xb = read();
		yb = read();
		int l = L, r = min(R, min(xb - xa + 1, yb - ya + 1));
		while(l < r)
		{
			int mid = (l + r + 1) / 2;
			if(query(xa + mid - 1, ya + mid - 1, xb, yb) >= mid)
			{
				l = mid;
			}
			else
			{
				r = mid - 1;
			}
		}
		printf("%d\n", l);
	}
	return 0;
}