434B

Description

A matrix with $n$ rows and $m$ columns consists of 1s and 0s. ($1 \leq n,m \leq 10^3$) Now, we have $q$ ($1 \leq q \leq 10^3$) 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 ($x,y$) on its edge. The rectangle must be filled with 1s.

Tutorial

We calculate $l[i][j]$ which is the length of the longest chain of 1s on the right of point ($i,j$). It can be done with $O(n^2)$ or $O(nm)$. For each change we can change $l$ in $O(n)$. For each query we can calculate largest rectangle with the point on its right side in $O(n)$.

If the point is ($x,y$), we start from the rectangle of a single line from ($x-l[x][y],y$) to ($x,y$). 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 $l[x-1][y]$ is larger than $l[x+1][y]$. 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;
}