CF1301 E. Nanosoft

发表于 | 阅读数

定义一个正方形$2r\times 2r$,左上角$r\times r$为红，右上角$r\times r$为绿，左下角$r*r$为黄，右下角$r\times r$为蓝：符合条件的正方形。

给一个随机颜色矩阵，询问$q$次：左上角$(x1,y1)$-右下角$(x2,y2)$中最大面积的这样正方形。$n\leq 500,q\leq3*10^5$

题目数据可知，通过预处理，使得询问$O(1)$或者$O(\log n)$。

  • 首先可以预处理$(x,y)$这个点是否存在$2r$的正方形。（通过不同颜色的二维前缀和$O(1)$判断)。

  • 对于一个左上角$(x1,y1)$-右下角$(x2,y2)$是否存在$2r$的正方形。可以预处理$2r$正方形的二维前缀和,然后计算即可。

  • 对于每个询问,由于存在$2r$的正方形，一定存在$2R,R<r$的正方形，存在单调性，就可以二分查询左上角$(x1+2mid,y1+2*mid)$-右下角$(x2,y2)$的区间是否存在$2mid$的正方形

$O(n^3+n\log n)$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
const int N = 500 + 10;
const int mod = 1e9 + 7;

int f[N][N][N];
int c[4][N][N];
int mp[200];
ll query(int sum[][N], int x1, int y1, int x2, int y2)
{
    return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
int n, m;
int main()
{
    mp['R'] = 0;
    mp['G'] = 1;
    mp['Y'] = 2;
    mp['B'] = 3;
    scanf("%d%d", &n, &m);
    int q;
    scanf("%d", &q);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char ch;
            cin >> ch;
            c[mp[ch]][i][j]++;
        }
    for (int t = 0; t < 4; t++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                c[t][i][j] += c[t][i - 1][j] + c[t][i][j - 1] - c[t][i - 1][j - 1];

    for (int k = 1; k <= min(n, m) / 2; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (i >= 2 * k && j >= 2 * k)
                {
                    int suma = query(c[0], i - 2 * k + 1, j - 2 * k + 1, i - k, j - k);
                    int sumb = query(c[1], i - 2 * k + 1, j - k + 1, i - k, j);
                    int sumc = query(c[2], i - k + 1, j - 2 * k + 1, i, j - k);
                    int sumd = query(c[3], i - k + 1, j - k + 1, i, j);
                    if (suma == k * k && sumb == k * k && sumc == k * k && sumd == k * k)
                        f[k][i][j]++;
                }
    for (int t = 1; t <= min(n, m) / 2; t++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                f[t][i][j] += f[t][i - 1][j] + f[t][i][j - 1] - f[t][i - 1][j - 1];
    while (q--)
    {
        int x1, y1, y2, x2;
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int l = 1, r = min((x2 - x1 + 1) / 2, (y2 - y1 + 1) / 2), ans = 0;
        while (l <= r)
        {
            int mid = (l + r) >> 1;
            //cout << l << " " << r << endl;
            // cout << mid << " " << query(f[mid], x1 + 2 * mid - 1, y1 + 2 * mid - 1, x2, y2) << endl;
            // cout << x1 + 2 * mid - 1 << " " << y1 + 2 * mid - 1 << " " << x2 << " " << y2 << endl;
            if (query(f[mid], x1 + 2 * mid - 1, y1 + 2 * mid - 1, x2, y2) > 0)
            {

                l = mid + 1;
                ans = mid;
            }
            else
            {
                r = mid - 1;
            }
        }
        printf("%d\n", ans * ans * 4);
    }
}