大致题意: 给你一个\(n*n\)的黑白棋盘,每次将一个格子翻转,分别求黑色连通块和白色连通块的个数。
\(LCT\)动态维护图连通性
关于这一部分内容,可以参考这道例题:【BZOJ4025】二分图。
大致思路
我们可以将同种颜色的相邻格子之间连边,这样就可以把问题搬到图上。
然后考虑先离线,把每两个格子间边的加入与删除的时间(同一条边可能被加入和删除多次)记录下来。
这样就可以用\(LCT\)动态维护图连通性了。
但注意这道题比较恶心,需要你每次求出两种颜色的连通块个数。
我一开始的想法是对于每个询问暴力枚举\(LCT\)的每一个根节点,判断其为黑色还是白色(我们可以给每条边也记录下对应的颜色),从而统计答案,但是毫无悬念地\(TLE\)了。
看来,只能在删边与加边的同时动态维护了。
在加边时,若连接的两个节点在不同的树中,就说明要合并两个连通块,因此将该颜色连通块个数减\(1\)。
在删边时,若连接的两个节点依靠这条边连通,即这条边原先并没有在\(LCT\)中被删掉过,就说明会使一个连通块分成两个,因此将该颜色连通块个数加\(1\)。
要注意的是,当你翻转一个格子时,要将原先颜色的连通块个数减\(1\),并将新颜色的连通块个数加\(1\),不然在加边删边的过程中会出现重复计算的问题。
具体实现可见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#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 1e9
using 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<pair<int,int>,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]<T.V[p]) return;
T.T[p]=0,T.Cut(tx[p],p),T.Cut(p,ty[p]),T.T[z]=1,T.Link(x,z),T.Link(z,y);
}
I void Del(CI pos)//删除一条边
{
RI x=o[pos].x,y=o[pos].y,z=o[pos].p;
!(T.FR(x)^T.FR(z))&&!(T.FR(y)^T.FR(z))&&(++ans[T.C[z]],T.T[z]=0,T.Cut(x,z),T.Cut(z,y),0);//分裂一个连通块,则将该颜色连通块个数加1
}
int main()
{
RI i,j,k=1,tot,cnt=0,p,nx,ny,p1,p2;Reg pair<int,int> 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;
}