codeforces248(div1) B ナナミのデジタルボード

q 回のクエリで、各クエリは行列の特定の値 (0 から 1、1 から 0) または クエリ部分行列の最大領域を変更することができ、この点が境界上にある必要があります。求められた部分行列、および部分行列 行列内の各ストアはすべて 1 です

点 (i,j) が上に進むことができる最長の高さを表すために up[i][j] を使用します。 ,j) が 0 の場合、up[i][j] の値は 0 になります

同様に、down、left、right の配列を維持します

。その後、クエリを実行するたびに、up[ から列挙します。 i][j] をサブ行列の高さとして 1 に設定し、[左右に展開] に進みます。 up[i][j - 1] >= up[i][j] の場合、左に 1 単位拡張できます。答えは (r - l - 1) * 高さです

同様に、4 つの方向は個別にカウントされます。Take

//#pragma comment(linker, "/STACK:102400000,102400000")
//HEAD
#include <cstdio>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>

#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <cstdlib>

using namespace std;
//LOOP
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
//STL
#define PB push_back
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;


#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define CPY(a, b) memcpy(a, b, sizeof(a))
#define FC(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); it++)
#define EQ(a, b) (fabs((a) - (b)) <= 1e-10)
#define ALL(c) (c).begin(), (c).end()
#define SZ(V) (int)V.size()
#define RIV(n, m, k, p) scanf("%d%d%d%d", &n, &m, &k, &p)
#define RV(n, m, k, p, q) scanf("%d%d%d%d%d", &n, &m, &k, &p, &q)
#define WI(n) printf("%d\n", n)
#define WS(s) printf("%s\n", s)
typedef vector <int> VI;
typedef unsigned long long ULL;
const double eps = 1e-10;
const LL MOD = 1e9 + 7;
const int maxn = 1010;

int ipt[maxn][maxn];
int up[maxn][maxn], dwn[maxn][maxn], rht[maxn][maxn], lft[maxn][maxn];
int len[maxn], n, m;

void update_col(int y)
{
    FE(i, 1, n)
        if (ipt[i][y])
            up[i][y] = up[i - 1][y] + 1;
        else    up[i][y] = 0;
    FED(i, n, 1)
        if (ipt[i][y])
            dwn[i][y] = dwn[i + 1][y] + 1;
        else
            dwn[i][y] = 0;
}

void update_row(int x)
{
    FE(j, 1, m)
        if (ipt[x][j])
            lft[x][j] = lft[x][j - 1] + 1;
        else    lft[x][j] = 0;
    FED(j, m, 1)
        if (ipt[x][j])
            rht[x][j] = rht[x][j + 1] + 1;
        else    rht[x][j] = 0;
}

int solve(int sta, int hei, int con)
{
    int lm = sta, rm = sta;
    int ans = 0;
    for (int h = hei; h >= 1; h--)
    {
        while (lm >= 1 && len[lm] >= h)
            lm--;
        while (rm <= con && len[rm] >= h)
            rm++;
        ans = max(ans, h * (rm - lm - 1));
    }
    return ans;
}

int main()
{
    //freopen("0.txt", "r", stdin);
    int q, x, y, op;
    cin >> n >> m >> q;
    FE(i, 1, n)
        FE(j, 1, m)
            RI(ipt[i][j]);
    FE(i, 1, n)
        update_row(i);
    FE(j, 1, m)
        update_col(j);
    while (q--)
    {
        RIII(op, x, y);
        if (op == 1)
        {
            ipt[x][y] ^= 1;
            update_row(x);
            update_col(y);
//            cout << "UP  " << endl;
//            FE(i, 1, n) {
//                FE(j, 1, m)
//                    cout << up[i][j] << &#39; &#39;;
//                    cout <<endl;
//            }
//            cout << "----" << endl;
//            cout << "right  " << endl;
//            FE(i, 1, n) {
//                FE(j, 1, m)
//                    cout << rht[i][j] << &#39; &#39;;
//                    cout <<endl;
//            }
//            cout << "----" << endl;
        }
        else
        {
            int ans = 0;
            FE(j, 1, m) len[j] = up[x][j];
            ans = max(ans, solve(y, len[y], m));
            FE(j, 1, m) len[j] = dwn[x][j];
            ans = max(ans, solve(y, len[y], m));
            FE(i, 1, n) len[i] = lft[i][y];
            ans = max(ans, solve(x, len[x], n));
            FE(i, 1, n) len[i] = rht[i][y];
            ans = max(ans, solve(x, len[x], n));
            WI(ans);
        }
    }
    return 0;
}

上記は codeforces248(div1) B Nanami のデジタル ボードの内容です。その他の関連コンテンツについては、PHP 中国語 Web サイト (www.php.cn) に注目してください。