Codeforces Round #619 (Div. 2) E. Nanosoft 最大合法正方形-蒲公英云

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

题目链接：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;
}