大致题意： 给你一个\(n*n\)的黑白棋盘，每次将一个格子翻转，分别求黑色连通块和白色连通块的个数。

\(LCT\)动态维护图连通性

关于这一部分内容，可以参考这道例题：。

大致思路

我们可以将同种颜色的相邻格子之间连边，这样就可以把问题搬到图上。

然后考虑先离线，把每两个格子间边的加入与删除的时间（同一条边可能被加入和删除多次）记录下来。

这样就可以用\(LCT\)动态维护图连通性了。

但注意这道题比较恶心，需要你每次求出两种颜色的连通块个数。

我一开始的想法是对于每个询问暴力枚举\(LCT\)的每一个根节点，判断其为黑色还是白色（我们可以给每条边也记录下对应的颜色），从而统计答案，但是毫无悬念地\(TLE\)了。

看来，只能在删边与加边的同时动态维护了。

在加边时，若连接的两个节点在不同的树中，就说明要合并两个连通块，因此将该颜色连通块个数减\(1\)。

在删边时，若连接的两个节点依靠这条边连通，即这条边原先并没有在\(LCT\)中被删掉过，就说明会使一个连通块分成两个，因此将该颜色连通块个数加\(1\)。

要注意的是，当你翻转一个格子时，要将原先颜色的连通块个数减\(1\)，并将新颜色的连通块个数加\(1\)，不然在加边删边的过程中会出现重复计算的问题。

具体实现可见代码。

代码

#include
    
     #define Tp template
     
      #define Ts template
      
       #define Reg register#define RI Reg int#define Con const#define CI Con int&#define I inline#define W while#define N 200#define M 10000#define E ((N*N<<2)+(M<<3))#define P(x,y) (((x)-1)*n+(y))#define swap(x,y) (x^=y^=x^=y)#define mp make_pair#define INF 1e9using namespace std;const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};int n,m,ans[2],a[N*N+5],s[N*N+5],qx[M+5],qy[M+5],tx[N*N+E+5],ty[N*N+E+5],lst[N*N+E+5];map
       
        
         ,int> t;struct Operate//存储下每一个操作{    int x,y,c,t,f,p,d;    I Operate(CI a=0,CI b=0,CI co=0,CI ti=0,CI fl=0):x(a),y(b),c(co),t(ti),f(fl){}}o[E+5];class FastIO{    private:        #define FS 100000        #define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)        #define pc(c) (C^FS?FO[C++]=c:(fwrite(FO,1,C,stdout),FO[(C=0)++]=c))        #define tn(x) (x<<3)+(x<<1)        #define D isdigit(c=tc())        int T,C;char c,*A,*B,FI[FS],FO[FS],S[FS];    public:        I FastIO() {A=B=FI;}        Tp I void read(Ty& x) {x=0;W(!D);W(x=tn(x)+(c&15),D);}        Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}        Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}        Tp I void writeln(Con Ty& x) {write(x),pc('\n');}        I void write_space() {pc(' ');}        I void clear() {fwrite(FO,1,C,stdout),C=0;}}F;class LinkCutTree//LCT{    private:        #define GVmin(x,y) (V[O[x].Min]>V[O[y].Min]&&(O[x].Min=O[y].Min))        #define PU(x) (O[x].Min=x,GVmin(x,O[x].S[0]),GVmin(x,O[x].S[1]))//上传子树信息        #define Re(x) (swap(O[x].S[0],O[x].S[1]),O[x].R^=1)        #define PD(x) (O[x].R&&(Re(O[x].S[0]),Re(O[x].S[1]),O[x].R=0))        #define Wh(x) (O[O[x].F].S[1]==x)        #define Co(x,y,d) (O[O[x].F=y].S[d]=x)        #define IR(x) (O[O[x].F].S[0]^x&&O[O[x].F].S[1]^x)        #define MR(x) (Ac(x),S(x),Re(x))        #define Sp(x,y) (MR(x),Ac(y),S(y))         static const int SZ=N*N+E;int St[SZ+5];struct node {int Min,R,F,S[2];}O[SZ+5];        I void Ro(CI x) {RI f=O[x].F,p=O[f].F,d=Wh(x);!IR(f)&&(O[p].S[Wh(f)]=x),O[x].F=p,Co(O[x].S[d^1],f,d),Co(f,x,d^1),PU(f),PU(x);}        I void S(CI x) {RI f=x,T=0;W(St[++T]=f,!IR(f)) f=O[f].F;W(T) PD(St[T]),--T;W(!IR(x)) f=O[x].F,!IR(f)&&(Ro(Wh(x)^Wh(f)?x:f),0),Ro(x);}        I void Ac(RI x) {for(RI s=0;x;x=O[s=x].F) S(x),O[x].S[1]=s,PU(x);}    public:        int C[SZ+5],V[SZ+5],T[SZ+5];I LinkCutTree() {V[0]=INF+1;}        I void Init(CI n) {for(RI i=1,s=n*n;i<=s;++i) V[O[i].Min=i]=INF+1,C[i]=a[i],T[i]=1;}//初始化每个点被删除时间为INF+1，记录其颜色，标记其在树中        I void Link(CI x,CI y) {MR(x),O[x].F=y;}I void Cut(CI x,CI y) {MR(x),Ac(y),S(x),O[y].F=O[x].S[1]=0,PU(x);}        I int FR(RI x) {Ac(x),S(x);W(O[x].S[0]) PD(x),x=O[x].S[0];return S(x),x;}        I int QMin(CI x,CI y) {return Sp(x,y),O[y].Min;}//查询子树中最早被删掉的边        I int Query(CI tot,CI op) {RI i,res=0;for(i=1;i<=tot;++i) T[i]&&!O[i].F&&!(C[i]^op)&&++res;return res;}//询问颜色为op的连通块个数（用于初始化ans）        I void RC(CI x) {C[x]^=1;}//翻转某个点的颜色}T;I void Add(CI pos)//加入一条边{    RI x=o[pos].x,y=o[pos].y,z=o[pos].p;    if(T.C[z]=o[pos].c,T.V[z]=o[pos].d,T.FR(x)^T.FR(y)) return --ans[T.C[z]],T.T[z]=1,T.Link(x,z),T.Link(z,y);//合并两个连通块，则将该颜色连通块个数减1    RI p=T.QMin(x,y);if(T.V[z]
         
           w; for(F.read(n),i=1;i<=n;++i) for(j=1;j<=n;++j) F.read(a[P(i,j)]),s[P(i,j)]=a[P(i,j)];//读入，用s数组复制一遍a数组 for(T.Init(n),i=1;i<=n;++i) for(j=1;j<=n;++j)//初始化出原图的边 { i^n&&!(a[P(i,j)]^a[P(i+1,j)])&&(o[++cnt]=Operate(P(i,j),P(i+1,j),a[P(i,j)],0,1),0),//向下 j^n&&!(a[P(i,j)]^a[P(i,j+1)])&&(o[++cnt]=Operate(P(i,j),P(i,j+1),a[P(i,j)],0,1),0);//向右 } for(F.read(m),i=1;i<=m;++i)//离线处理出每个加边和删边操作 { for(F.read(qx[i],qy[i]),a[p=P(qx[i],qy[i])]^=1,j=0;j^4;++j) { if((nx=qx[i]+dx[j])<1||nx>n||(ny=qy[i]+dy[j])<1||ny>n) continue; p1=p,p2=P(nx,ny),p1>p2&&swap(p1,p2),o[++cnt]=Operate(p1,p2,a[p1]^a[p2]?-1:a[p1],i,a[p1]^a[p2]?-1:1); } } for(tot=n*n,i=1;i<=cnt;++i) !t[w=mp(o[i].x,o[i].y)]&&(t[w]=++tot,tx[t[w]]=o[i].x,ty[t[w]]=o[i].y),o[i].p=t[w];//给边标号，这样便于将边看作一个节点 for(i=cnt;i;--i) ~o[i].f?(o[i].d=lst[o[i].p]?lst[o[i].p]:INF):(lst[o[i].p]=o[i].t);//倒序枚举，求出每条边的出现和删除时间 W(k<=cnt&&!o[k].t) Add(k++);//先将原图的边加到图上 for(ans[0]=T.Query(tot,0),ans[1]=T.Query(tot,1),i=1;i<=m;++i)//初始化ans，然后处理操作 { p=P(qx[i],qy[i]),--ans[s[p]],++ans[s[p]^=1],T.RC(p);W(k<=cnt&&!(o[k].t^i)) ~o[k].f?Add(k++):Del(k++);//更新信息 F.write(ans[1]),F.write_space(),F.writeln(ans[0]);//输出答案 } return F.clear(),0;}