动态图联通性模板题写了一个多小时……
就是线段树分治 维护黑白两种图
然后我初始化的时候忘记size设成１T成狗
#include<bits/stdc++.h>
using namespace std;
#define fp(i,l,r) for(register int (i)=(l);(i)<=(r);++(i))
#define fd(i,l,r) for(register int (i)=(l);(i)>=(r);--(i))
#define fe(i,u) for(register int (i)=front[(u)];(i);(i)=e[(i)].next)
#define O(x) cerr<<#x<<':'<<x<<endl
#define mem(a) memset((a),0,sizeof (a))
//#define int long long
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
void wr(int x){
if(x<0)putchar('-'),x=-x;
if(x>=10)wr(x/10);
putchar('0'+x%10);
}
const int MAXN=40100,MAXM=10010;
struct DSU{
int fa[MAXN],sze[MAXN],sta[MAXN],top,cnt;
inline int getf(int x){
while(x!=fa[x])x=fa[x];
return x;
}
inline void merge(int x,int y){
x=getf(x);y=getf(y);if(x==y)return;
if(sze[x]>sze[y])swap(x,y);fa[x]=y;sze[y]+=sze[x];
sta[++top]=x;++cnt;
}
inline void goback(int g){
while(top!=g){
int x=sta[top--],y=fa[x];
sze[y]-=sze[x];fa[x]=x;--cnt;
}
}
}B,W;
#define lson o<<1
#define rson o<<1|1
struct node{
int u,v,c;
};
vector<node>buc[MAXM<<2];
int tot,cntw[MAXM];
void solve(int o,int l,int r){
int top1=B.top,top2=W.top;
for(auto x:buc[o]){
int c=x.c,u=x.u,v=x.v;
if(c)B.merge(u,v);
else W.merge(u,v);
}
if(l==r){
if(l)printf("%d %d
",tot-cntw[l]-B.cnt,cntw[l]-W.cnt);
B.goback(top1);W.goback(top2);return;
}
int mid=l+r>>1;
solve(lson,l,mid);solve(rson,mid+1,r);
B.goback(top1);W.goback(top2);
}
const int fx[4]={0,1,0,-1},fy[4]={1,0,-1,0};
map<pair<int,int>,int>mp;
int n,m;
void pushinfo(int o,int l,int r,int ql,int qr,node x){
if(ql<=l&&r<=qr){buc[o].push_back(x);return;}
int mid=l+r>>1;
if(ql<=mid)pushinfo(lson,l,mid,ql,qr,x);
if(qr>mid)pushinfo(rson,mid+1,r,ql,qr,x);
}
inline void Cut(int c,int u,int v,int tim){
if(u>v)swap(u,v);
pushinfo(1,0,m,mp[{u,v}],tim-1,{u,v,c});
}
inline void Link(int u,int v,int tim){
if(u>v)swap(u,v);
mp[{u,v}]=tim;
}
int col[205][205],id[202][202];
inline bool check(int x,int y){
return x<=n&&y<=n&&x>=1&&y>=1;
}
main(){
n=read();
fp(i,1,n)fp(j,1,n){
col[i][j]=read(),id[i][j]=++tot;
if(col[i][j]==0)++cntw[0];
}
fp(i,1,n)fp(j,1,n){
fp(k,0,3){
int xx=i+fx[k],yy=j+fy[k];
if(!check(xx,yy)||col[xx][yy]!=col[i][j])continue;
Link(id[xx][yy],id[i][j],0);
}
}
fp(i,1,tot)B.fa[i]=i,W.fa[i]=i,B.sze[i]=i,W.sze[i]=i;
m=read();
fp(i,1,m){
int x=read(),y=read(),c=col[x][y];cntw[i]=cntw[i-1];
fp(k,0,3){
int xx=x+fx[k],yy=y+fy[k];
if(!check(xx,yy)||col[xx][yy]!=c)continue;
Cut(c,id[xx][yy],id[x][y],i);
}
if(!c)--cntw[i];
col[x][y]^=1;c=col[x][y];
if(!c)++cntw[i];
fp(k,0,3){
int xx=x+fx[k],yy=y+fy[k];
if(!check(xx,yy)||col[xx][yy]!=c)continue;
Link(id[xx][yy],id[x][y],i);
}
}
fp(i,1,n)fp(j,1,n){
fp(k,0,3){
int xx=i+fx[k],yy=j+fy[k];
if(!check(xx,yy)||col[xx][yy]!=col[i][j])continue;
Cut(col[i][j],id[xx][yy],id[i][j],m+1);
}
}
solve(1,0,m);
return 0;
}