先膜一下大佬->这里
据说这题正解是LCT，然而感觉还是线段树套并查集的更容易理解
我们对于行与行之间用线段树维护，每一行内用并查集暴力枚举
每一行内用并查集暴力枚举连通块这个应该容易理解，就是如果是同一个同色连通块的就用并查集连起来。那么怎么处理行与行之间的连通块嘞？
因为几行连起来可以看做一块，那么我们用$[1,n]$维护最上面一行的连通性，用$[n+1,n*2]$维护最下面一行的连通性，然后用$[n*2+1,n*4]$作为辅助
这一部分的细节还是看代码好了，写在注解里了
//minamoto
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
const int N=;
int n,m;
int chess[N][N],mp[N<<];
struct node{
int fa[N<<];
inline void init(){for(int i=;i<=(n<<);++i) fa[i]=i;}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
inline void unique(int x,int y){fa[find(x)]=find(y);}
inline bool check(int x,int y){return find(x)==find(y);}
}data[N<<];
int wh[N],bl[N],L[N],R[N];
void pushup(int p){
int mid=L[p]+R[p]>>;
wh[p]=wh[p<<]+wh[p<<|];
bl[p]=bl[p<<]+bl[p<<|];
data[p].init();
for(int i=;i<=(n<<);++i){
data[p].unique(i,data[p<<].find(i));
//1~n记录左儿子最上面一行连通性
//n+1~n*2记录左儿子最下面一行的连通性
data[p].unique(i+(n<<),data[p<<|].find(i)+(n<<));
//n*2+1~n*3记录右儿子最上面一行连通性
//n*3+1~n*4记录左儿子最下面一行的连通性
}
//枚举左右儿子交界处是否有新的连通块
for(int i=;i<=n;++i)
if(chess[mid][i]==chess[mid+][i]){
if(data[p].check(i+n,i+(n<<))) continue;
data[p].unique(i+n,i+(n<<));
wh[p]-=chess[mid][i]^;
bl[p]-=chess[mid][i];
}
//下面这一段就是把所有节点的父亲都赋值为下标最小的点
//顺便记录最上面一行和最下面一行的连通性
for(int i=;i<=(n<<);++i)
data[p].find(i),mp[i]=;
for(int i=;i<=n;++i)
if(!mp[data[p].fa[i]])
mp[data[p].fa[i]]=i,data[p].fa[i]=i;
else data[p].fa[i]=mp[data[p].fa[i]];
for(int i=n*+;i<=(n<<);++i)
if(!mp[data[p].fa[i]])
mp[data[p].fa[i]]=i-(n<<),data[p].fa[i]=i-(n<<);
else data[p].fa[i]=mp[data[p].fa[i]];
for(int i=;i<=n;++i) data[p].fa[i+n]=data[p].fa[i+n*];//记录一下这一块最下面一行的连通性
}
void build(int p,int l,int r){
L[p]=l,R[p]=r;
if(l==r){
wh[p]=chess[l][]^;
bl[p]=chess[l][];
data[p].init();
data[p].unique(+n,);
for(int i=;i<=n;++i){
data[p].unique(i+n,i);
if(chess[l][i-]==chess[l][i]) data[p].unique(i,i-);
else wh[p]+=chess[l][i]^,bl[p]+=chess[l][i];
}
return;
}
int mid=l+r>>;
build(p<<,l,mid),build(p<<|,mid+,r);
pushup(p);
}
void update(int x,int p){
if(L[p]==R[p]){
wh[p]=chess[x][]^;
bl[p]=chess[x][];
data[p].init();
data[p].unique(n+,);
for(int i=;i<=n;++i){
data[p].unique(i+n,i);
if(chess[x][i-]==chess[x][i]) data[p].unique(i,i-);
else wh[p]+=chess[x][i]^,bl[p]+=chess[x][i];
}
return;
}
int mid=L[p]+R[p]>>;
if(x<=mid) update(x,p<<);
else update(x,p<<|);
pushup(p);
}
int main(){
//freopen("testdata.in","r",stdin);
n=read();
for(int i=;i<=n;++i) for(int j=;j<=n;++j)
chess[i][j]=read();
build(,,n);
m=read();
while(m--){
int x=read(),y=read();
chess[x][y]^=;
update(x,);
printf("%d %d\n",bl[],wh[]);
}
return ;
}