题解：B4229 [常州市赛 2024] 棋盘

· · 题解

开始时答案为 n\times n，我们不妨在每个操作后加减答案。

先考虑特殊性质：只用考虑行或列。

显然行和列是完全一样的，因为黑白全部交换是没变化的。为了方便说明，我们只考虑行。

此时在任意时刻，每列一定是 n 个联通块。因此每次操作只会改变第 x 行分别与其上下两行是否联通，若原本联通，则操作后不联通，答案减 n，相反答案加 n。

写完特殊性质和暴力后，直接就可以拿到 90 分！接下来我们考虑正解。

正解和特殊性质差异不大。特殊性质是直接考虑了一整行，这是因为一行内一定是 n 个联通块，因此正解就需要考虑每一行有多少个联通块，显然每一行的联通块数量都是相同的，这个是列操作影响的，与列操作使答案的加减同步。

列操作与行操作本质相同，便不再说明，下面展示代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
bool f1[100010],f2[100010];//分别表示行和列是否被操作过 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,q;
    cin>>n>>q;
    ll ans=n*n;//答案 
    ll l=0,r=0;//分别统计每一列的联通块数量和每一行的联通块数量 
    while(q--)
    {
        ll op,x;
        cin>>op>>x;
        if(op==1)
        {
            f1[x]=!f1[x];//更新状态 
            if(x>1)//边界 
            {
                if(f1[x]==f1[x-1])ans+=n+r,l++;//若两行保持同步，则说明不联通，答案变大 
                else ans-=n+r,l--;//若两行不保存同步，则说明联通，答案变小 
            }
            if(x<n)//边界 
            {
                if(f1[x]==f1[x+1])ans+=n+r,l++;
                else ans-=n+r,l--;
            }
        }
        else
        {
            f2[x]=!f2[x];
            if(x>1)
            {
                if(f2[x]==f2[x-1])ans+=n+l,r++;
                else ans-=n+l,r--;
            }
            if(x<n)
            {
                if(f2[x]==f2[x+1])ans+=n+l,r++;
                else ans-=n+l,r--;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}