Codeforces Round #619 (Div. 2) E. Nanosoft 最大合法正方形

阳光穿透心脏的1/2处 2023-07-15 13:25 16阅读 0赞

题目链接：http://codeforces.com/contest/1301/problem/E  
题意：对于一个正方形分成4等份，左上角红，右上角绿，左下角黄，右下角蓝才认为合法的，对于  
给定的矩形，询问你这个矩形中最大的合法正方形面积  
思路：用二维前缀和统计方块，正方形边长最大250，枚举边长，每次检查左上角个数是否为l\*l,  
其余角同样，做个前缀和可以O(1)判断

如果范围再大些我们可以用考虑二分+二维ST表，因为每个大的合法正方形必然包含一个小的合法正方形，满足单调性

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define fi first
    #define se second
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    #define pll pair<ll, ll>
    #define pii pair<int, int>
    #define ull unsigned long long
    #define pdd pair<double, double>
    const int mod = 1e9 + 7;
    const int maxn = 3e5 + 10;
    const int inf = 0x3f3f3f3f;
    int cnt[5][505][505], r1[maxn], c1[maxn], r2[maxn], c2[maxn], ans[maxn];
    char s[505][505];
    int n, m, q;
    int check(int k, int x1, int y1, int x2, int y2)
    {
        return cnt[k][x2][y2] - cnt[k][x1 - 1][y2] - cnt[k][x2][y1 - 1] + cnt[k][x1 - 1][y1 - 1];
    }
    int main()
    {
        scanf("%d%d%d", &n, &m, &q);
        for(int i = 1; i <= n; ++i)
        {
            scanf("%s", s[i] + 1);
            for(int j = 1; j <= m; ++j)
            {
                if(s[i][j] == 'R') cnt[0][i][j] = 1;
                if(s[i][j] == 'G') cnt[1][i][j] = 1;
                if(s[i][j] == 'Y') cnt[2][i][j] = 1;
                if(s[i][j] == 'B') cnt[3][i][j] = 1;
            }
        }
        for(int k = 0; k <= 3; ++k)
        {
            for(int i = 1; i <= n; ++i) //前缀和
                for(int j = 1; j <= m; ++j)
                    cnt[k][i][j] += cnt[k][i - 1][j];
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                    cnt[k][i][j] += cnt[k][i][j - 1];
        }
        for(int i = 1; i <= q; ++i) scanf("%d%d%d%d", &r1[i], &c1[i], &r2[i], &c2[i]);
        for(int l = 1; l <= 250; ++l)
        {
            if(2 * l > n || 2 * l > m) break;
            for(int i = 1; i <= n; ++i)
                for(int j = 1; j <= m; ++j)
                    cnt[4][i][j] = 0;
            for(int i = 1; i <= n - 2 * l + 1; ++i) //判断是否存在合法正方形
            {
                for(int j = 1; j <= m - 2 * l + 1; ++j)
                {
                    if(check(0, i, j, i + l - 1, j + l - 1) == l * l && check(1, i, j + l, i + l - 1, j + 2 * l - 1) == l * l)
                    {
                        if(check(2, i + l, j , i + 2 * l - 1, j + l - 1) == l * l && check(3, i + l, j + l, i + 2 * l - 1, j + 2 * l - 1) == l * l)
                            cnt[4][i][j] = 1;
                    }
                }
            }
            for(int i = 1; i <= n - 2 * l + 1; ++i) //前缀和
                for(int j = 1; j <= m - 2 * l + 1; ++j)
                    cnt[4][i][j] += cnt[4][i - 1][j];
            for(int i = 1; i <= n - 2 * l + 1; ++i)
                for(int j = 1; j <= m - 2 * l + 1; ++j)
                    cnt[4][i][j] += cnt[4][i][j - 1];
            for(int i = 1; i <= q; ++i)
            {
                if(r2[i] - r1[i] + 1 >= 2 * l && c2[i] - c1[i] + 1 >= 2 * l && check(4, r1[i], c1[i], r2[i] - 2 * l + 1, c2[i] - 2 * l + 1) > 0)
                    ans[i] = l;
            }
        }
        for(int i = 1; i <= q; ++i)
            printf("%d\n", 4 * ans[i] * ans[i]);
        return 0;
    }