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

feifeize · 2025-10-22 17:30:58 · 题解

对于这一题，首先对于每一行每一列维护联通，在线编写每次修改当前行状态数，然后相乘就行了。

怎么维护呢？

1：修改的是边界的

分类讨论：若与最近的一样，当前的联通数 +1，否则 -1。

2：修改中间

照样分类：若只与左右其中一个一样，当前的联通数不变；若都一样，则当前的联通数 +2；若都不一样，则当前的联通数 -2。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+7;

int n,q,a,b,hh,ll, h[N],l[N];

signed main()
{
    cin>>n>>q;

    for(int i=1;i<=n;i++)h[i]=l[i]=(i%2==1)?0:1;
    h[0]=h[n+1]=l[0]=l[n+1]=2;
    hh=n,ll=n;
    while(q--)
    {
        cin>>a>>b;
        if(a==1) 
        {

            if(b==1||b==n)
            {
                if(h[b-1]!=h[b]&&h[b+1]!=h[b])hh-=1;
                else hh+=1;
            }
            else if(h[b-1]==h[b]&&h[b+1]==h[b])hh+=2;
            else if(h[b-1]!=h[b]&&h[b+1]!=h[b])hh-=2;
            h[b]=(h[b]+1)%2; 
        }
        else 
        {
            if(b==1||b==n)
            {
                if(l[b-1]!=l[b]&&l[b+1]!=l[b])ll-=1;
                else ll+=1;
            }
            else if(l[b-1]==l[b]&&l[b+1]==l[b])ll+=2;
            else if(l[b-1]!=l[b]&&l[b+1]!=l[b])ll-=2;
            l[b]=(l[b]+1)%2;
        }
        cout<<ll*hh<<endl; 
    }
}