434B


  Posted on 10 Dec 2014
dynamic programming implementation

Description


A matrix with rows and columns consists of 1s and 0s. () Now, we have () operations. There are two kinds of operations. First is to change the value of one point in the matrix (1 to 0 or 0 to 1). Second is to query what is the largest space of a rectangle with point () on its edge. The rectangle must be filled with 1s.

Tutorial


We calculate which is the length of the longest chain of 1s on the right of point (). It can be done with or . For each change we can change in . For each query we can calculate largest rectangle with the point on its right side in .

If the point is (), we start from the rectangle of a single line from () to (). Then we strech it up and down one unit at a time. Of course the left side of the rectangle may be pushed right during the strech. In each strech, we choose up if is larger than . Otherwise, we strech down. Each time we calculate the space of the rectangle and update the answer.

It is the same when the point is on the left, up and down side of the rectangle.

Solution


#include <cstdio>
#include <algorithm>
using namespace std;

#define D(x) x

const int MAX_N = 1050;
const int MAX_M = 1050;

int n, m, q;
int matrix[MAX_N][MAX_M];
int l[MAX_M][MAX_N];
int r[MAX_M][MAX_N];
int u[MAX_N][MAX_M];
int d[MAX_N][MAX_M];

void modify(int x, int y)
{
	matrix[x][y] ^= 1;
	for (int j = 1; j <= m; j++)
	{
		if (matrix[x][j] == 1)
		{
			l[j][x] = l[j - 1][x] + 1;
		}else
		{
			l[j][x] = 0;
		}
	}
	for (int j = m; j >= 1; j--)
	{
		if (matrix[x][j] == 1)
		{
			r[j][x] = r[j + 1][x] + 1;
		}else
		{
			r[j][x] = 0;
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (matrix[i][y] == 1)
		{
			u[i][y] = u[i - 1][y] + 1;
		}else
		{
			u[i][y] = 0;
		}
	}
	for (int i = n; i >= 1; i--)
	{
		if (matrix[i][y] == 1)
		{
			d[i][y] = d[i + 1][y] + 1;
		}else
		{
			d[i][y] = 0;
		}
	}
}

int query(int f[], int pos, int bound)
{
	int l = pos;
	int r = pos;
	int ret = f[pos];
	int min_height = f[pos];
	while (l > 1 || r < bound)
	{
		if (r == bound || f[l - 1] > f[r + 1])
		{
			l--;
			min_height = min(min_height, f[l]);
		}else
		{
			r++;
			min_height = min(min_height, f[r]);
		}
		ret = max(ret, (r - l + 1) * min_height);
	}
	return ret;
}

int main()
{
	//input
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", matrix[i] + j);

	//prework
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
		{
			if (matrix[i][j] == 1)
			{
				l[j][i] = l[j - 1][i] + 1;
				u[i][j] = u[i - 1][j] + 1;
			}else
			{
				l[j][i] = u[i][j] = 0;
			}
		}

	for (int i = n; i >= 1; i--)
		for (int j = m; j >= 1; j--)
		{
			if (matrix[i][j] == 1)
			{
				r[j][i] = r[j + 1][i] + 1;
				d[i][j] = d[i + 1][j] + 1;
			}else
			{
				d[i][j] = r[j][i] = 0;
			}
		}

	//work
	while (q--)
	{
		int a, x, y;
		scanf("%d%d%d", &a, &x, &y);
		if (a == 1)
		{
			modify(x, y);
			continue;
		}
		int ans = 0;
		ans = max(ans, query(l[y], x, n));
		ans = max(ans, query(r[y], x, n));
		ans = max(ans, query(u[x], y, m));
		ans = max(ans, query(d[x], y, m));
		printf("%d\n", ans);
	}
	return 0;
}