P14537 [OII 2025] 双色金字塔 / Piramide bicolore

· · 题解

我们每次询问需要求的是，初始矩阵的一个子矩阵 [x, x + h] \times [y, y + h] 作为金字塔的最底层，塔顶的颜色是什么。

手玩 n \le 5 的矩阵很难不发现，塔顶是黑色当且仅当：

如下：

100??    011??    ??001    ??110
0100?    1011?    ?0010    ?1101
00100    11011    00100    11011
?0010    ?1101    0100?    1011?
??001    ??110    100??    011??

判断第一种情况，可以令 a_{i, j} 表示是否满足 (i, j), (i + 1, j + 1), (i + 2, j + 2) 都是 1 且 (i, j + 1), (i, j + 2), (i + 1, j), (i + 1, j + 2), (i + 2, j), (i + 2, j + 1) 都是 0，然后做一个对角线的前缀和。另外三种情况同理。

注意特判 h = 1。

时间复杂度 O(n^2 + q)。

:::info[代码]

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5050;

int n, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn], d[maxn][maxn];
char s[maxn][maxn];

void init(int _n, vector<string> _s) {
    n = _n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            s[i][j] = _s[i - 1][j - 1];
        }
    }
    for (int i = 1; i <= n - 2; ++i) {
        for (int j = 1; j <= n - 2; ++j) {
            a[i][j] = (s[i][j] == '1' && s[i][j + 1] == '0' && s[i][j + 2] == '0' && s[i + 1][j] == '0' && s[i + 1][j + 1] == '1' && s[i + 1][j + 2] == '0' && s[i + 2][j] == '0' && s[i + 2][j + 1] == '0' && s[i + 2][j + 2] == '1');
            b[i][j] = (s[i][j] == '0' && s[i][j + 1] == '1' && s[i][j + 2] == '1' && s[i + 1][j] == '1' && s[i + 1][j + 1] == '0' && s[i + 1][j + 2] == '1' && s[i + 2][j] == '1' && s[i + 2][j + 1] == '1' && s[i + 2][j + 2] == '0');
        }
        for (int j = 3; j <= n; ++j) {
            c[i][j] = (s[i][j] == '1' && s[i][j - 1] == '0' && s[i][j - 2] == '0' && s[i + 1][j] == '0' && s[i + 1][j - 1] == '1' && s[i + 1][j - 2] == '0' && s[i + 2][j] == '0' && s[i + 2][j - 1] == '0' && s[i + 2][j - 2] == '1');
            d[i][j] = (s[i][j] == '0' && s[i][j - 1] == '1' && s[i][j - 2] == '1' && s[i + 1][j] == '1' && s[i + 1][j - 1] == '0' && s[i + 1][j - 2] == '1' && s[i + 2][j] == '1' && s[i + 2][j - 1] == '1' && s[i + 2][j - 2] == '0');
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            a[i][j] += a[i - 1][j - 1];
            b[i][j] += b[i - 1][j - 1];
        }
        for (int j = n; j; --j) {
            c[i][j] += c[i - 1][j + 1];
            d[i][j] += d[i - 1][j + 1];
        }
    }
}

bool query(int k, int x, int y) {
    ++x;
    ++y;
    if (k == 1) {
        return s[x][y] == s[x + 1][y + 1] && s[x + 1][y] == s[x][y + 1] && s[x][y] != s[x + 1][y];
    }
    int p = x + k, q = y + k;
    if (a[p - 2][q - 2] - a[x - 1][y - 1] == k - 1) {
        return 1;
    }
    if (b[p - 2][q - 2] - b[x - 1][y - 1] == k - 1) {
        return 1;
    }
    if (c[p - 2][y + 2] - c[x - 1][q + 1] == k - 1) {
        return 1;
    }
    if (d[p - 2][y + 2] - d[x - 1][q + 1] == k - 1) {
        return 1;
    }
    return 0;
}

:::