Singularity

xzy_sf · 2025-11-21 15:44:56 · 题解

Analysis

首先让我们思考，什么情况下，四个块可以合成一个黑色的块？你会发现只有可能有两种情况，如下。

那么 O(n^3) 的方法就很明了了，我们通过每一层的信息，来依次更新上面一层的。如果是以上两种情况，就为 1，否则为 0。

接下来不妨思考一下，什么时候一个块是黑色的？

我们会发现，基座以上的每一个块的状态，都对应着基座的一个正方形区间，例如：

你会发现它们的左上端点坐标一致，且边长为 h+1。

那么接下来探索一下这个对应正方形区间的性质。可以手玩一下 n=5 及以上的正方形，你会发现，这个位置是黑色的，当且仅当：

• 有一条白色或黑色的对角线贯穿正方形；

• 没有多余的与对角线同色的的格子，在对角线任一格子的八连通范围之内。

这个很好理解，比方说我们在一个上方的黑格子，那么它的下一层，一定形如我们最开始说的两种情形。而这两种情况的黑格子，我们将其继续拆开到再下面一层……逐渐的展开，就会成为一条对角线了。

为什么不能有多余的格子在对角线的八连通范围之内呢？因为这样要不然会阻挡对角线的形成，要不然会在上面一层多形成一条对角线，阻挡上面一层对角线的形成。

Method

怎么实现？我们考虑预处理矩阵两个方向的对角线的前缀和即可。

对于第二个约束，我们可以将其转化为：当前正方形的上面两条对角线以及下面两条对角线都是当前对角线的反色，于是也可以用前缀和算了。

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

Code

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define il inline
#define pb push_back
#define llINF 0x3f3f3f3f3f3f3f3f
#define pii pair<int,int>
#define fi first
#define se second
#define mpr make_pair
using namespace std;
const int NN=5e3+10;
int n,q;
int mt[NN][NN],sum1[NN<<1][NN],sum2[NN<<1][NN];
void init(int N, vector<string> M){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    n=N;
    for(int i=1;i<=n;i++){
        string s;
        s=M[i-1];
        s=" "+s;
        for(int j=1;j<=n;j++) mt[i][j]=s[j]-'0';
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            sum1[j-i+n][j]=sum1[j-i+n][j-1]+mt[i][j];
        } 
    }
    for(int i=n;i>=1;i--){
        for(int j=1;j<=n;j++){
            sum2[i+j][j]=sum2[i+j][j-1]+mt[i][j];
        }
    }
}

bool query(int h, int x, int y) {
    x++,y++;
    if(h==0){
        return mt[x][y];
    }
    if(h==1){
        if((mt[x][y]&&mt[x+1][y+1]&&!mt[x][y+1]&&!mt[x+1][y]) || (!mt[x][y]&&!mt[x+1][y+1]&&mt[x][y+1]&&mt[x+1][y])) return 1;
        else return 0;
    }

    //case1&case2
    int val1,val2,val3,val4,val5;
    val1=sum1[y-x-2+n][y+h-2]-sum1[y-x-2+n][y-1];
    val2=sum1[y-x-1+n][y+h-1]-sum1[y-x-1+n][y-1];
    val3=sum1[y-x+n][y+h]-sum1[y-x+n][y-1];
    val4=sum1[y-x+1+n][y+h]-sum1[y-x+1+n][y];
    val5=sum1[y-x+2+n][y+h]-sum1[y-x+2+n][y+1];
    if((!val3&&val2==h&&val4==h&&val1==h-1&&val5==h-1) || (val3==h+1&&!val2&&!val4&&!val1&&!val5)) return 1;

    //case3&case4
    val3=sum2[x+y+h][y+h]-sum2[x+y+h][y-1];
    val2=sum2[x+y+h-1][y+h-1]-sum2[x+y+h-1][y-1];
    val1=sum2[x+y+h-2][y+h-2]-sum2[x+y+h-2][y-1];
    val4=sum2[x+y+h+1][y+h]-sum2[x+y+h+1][y];
    val5=sum2[x+y+h+2][y+h]-sum2[x+y+h+2][y+1];
    if((!val3&&val2==h&&val4==h&&val1==h-1&&val5==h-1) || (val3==h+1&&!val2&&!val4&&!val1&&!val5)) return 1;
    return 0;
}
#ifndef ONLINE_JUDGE

int main() {
    int N, Q;
    cin >> N >> Q;

    vector<string> M(N);
    for (int i = 0; i < N; i++)
        cin >> M[i];

    init(N, M);

    for (int i = 0; i < Q; i++) {
        int h, x, y;
        cin >> h >> x >> y;
        cout << query(h, x, y) << '\n';
    }
}

#endif