离线LCT维护MST，和3082的方法一样。然而比较码农，适合颓废的时候写。
PS：线段树分治要好写得多，LCT比较自娱自乐。
#include<bits/stdc++.h>
using namespace std;
const int dx[]={-1,1,0,0};
const int dy[]={0,0,-1,1};
const int inf=1e9;
int n;
int cal1(int x1,int y1,int x2,int y2){
int i=(min(x1,x2)*n+min(y1,y2))*2;
return x1==x2?i:i+1;
}
struct node;
typedef node*ptr;
struct vec{
int v;ptr i,s,t;
vec(){v=inf;}
};
bool operator<(vec a,vec b){
return a.v<b.v;
}
struct node{
ptr i,j,p;bool r;vec v,s;
node();
ptr up(){
s=min(min(v,i->s),j->s);
return this;
}
void down(){
if(r)
i->r^=1,j->r^=1,swap(i,j),r=0;
}
}e[120000];
node::node(){i=j=p=e;}
bool root(ptr o){
return o!=o->p->i&&o!=o->p->j;
}
void turn(ptr o){
ptr s=o->p,t=s->p;
if(!root(s))(s==t->i?t->i:t->j)=o;
o->p=t,s->p=o;
if(o==s->i)
s->i=o->j,o->j->p=s,o->j=s->up();
else
s->j=o->i,o->i->p=s,o->i=s->up();
}
void push(ptr o){
if(!root(o))push(o->p);
o->down();
}
ptr splay(ptr o){
push(o);
while(!root(o)){
if(!root(o->p))turn(o==o->p->i^o->p==o->p->p->i?o:o->p);
turn(o);
}
return o->up();
}
ptr exp(ptr o){
ptr s=e;
while(o!=e)splay(o)->j=s,s=o->up(),o=o->p;
return s;
}
ptr bel(ptr o){
o=exp(o);
while(o->i!=e)o=o->i,o->down();
return o;
}
bool jud(ptr s,ptr t){
exp(s)->r=1;
return bel(t)==s;
}
void link(ptr s,ptr t){
exp(s)->r=1,splay(s)->p=t;
}
bool cut(ptr s,ptr t){
exp(s)->r=1,exp(t);
splay(t);
if(s==t->i&&s->j==e)
return t->i=s->p=e;
return 0;
}
ptr cal2(int i){
return e+n*n+i+1;
}
bool link(int x1,int y1,int x2,int y2){
ptr s=e+x1*n+y1+1;
ptr t=e+x2*n+y2+1;
int i=cal1(x1,y1,x2,y2);
if(!jud(s,t)){
link(s,cal2(i));
link(t,cal2(i));
return 1;
}
exp(s)->r=1;
vec v=exp(t)->s;
if(v<cal2(i)->v){
cut(v.s,v.i);
cut(v.t,v.i);
link(s,cal2(i));
link(t,cal2(i));
}
return 0;
}
bool cut(int x1,int y1,int x2,int y2){
ptr s=e+x1*n+y1+1;
ptr t=e+x2*n+y2+1;
int i=cal1(x1,y1,x2,y2);
if(cut(s,cal2(i)))
return cut(t,cal2(i));
return 0;
}
int m,t,c6[2],c1[200][200];
queue<int>c3[80000];
void pre(int x1,int y1,int x2,int y2){
if(!~x1||x1==n||!~y1||y1==n||!~x2||x2==n||!~y2||y2==n)
return;
int i=cal1(x1,y1,x2,y2);
if(c1[x1][y1]==c1[x2][y2])
c3[i].push(t);
}
void ins(int x1,int y1,int x2,int y2){
if(!~x1||x1==n||!~y1||y1==n||!~x2||x2==n||!~y2||y2==n)
return;
int i=cal1(x1,y1,x2,y2);
if(c1[x1][y1]==c1[x2][y2]){
cal2(i)->v.i=cal2(i);
cal2(i)->v.s=e+x1*n+y1+1;
cal2(i)->v.t=e+x2*n+y2+1;
if(c3[i].empty())
cal2(i)->v.v=inf;
else{
cal2(i)->v.v=c3[i].front();
c3[i].pop();
}
if(link(x1,y1,x2,y2))
--c6[c1[x1][y1]];
}
}
void del(int x1,int y1,int x2,int y2){
if(0<=x1&&x1<n&&0<=y1&&y1<n&&0<=x2&&x2<n&&0<=y2&&y2<n&&c1[x1][y1]==c1[x2][y2]&&cut(x1,y1,x2,y2))
++c6[c1[x1][y1]];
}
struct que{int x,y;};
que c2[10000];
int main(){
struct{
operator int(){
int x=0,c=getchar();
while(c<48)c=getchar();
while(c>32)
x=x*10+c-48,c=getchar();
return x;
}
}it;
n=it;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
++c6[c1[i][j]=it];
m=it;
for(int&i=t=0;i<m;++i){
int x=it-1,y=it-1;
c2[i].x=x,c2[i].y=y;
for(int j=0;j<4;++j)
pre(x,y,x+dx[j],y+dy[j]);
c1[x][y]^=1;
}
for(int i=m-1;~i;--i)
c1[c2[i].x][c2[i].y]^=1;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j){
ins(i,j,i,j+1);
ins(i,j,i+1,j);
}
for(int i=0;i<m;++i){
int x=c2[i].x,y=c2[i].y;
for(int j=0;j<4;++j)
del(x,y,x+dx[j],y+dy[j]);
--c6[c1[x][y]];
++c6[c1[x][y]^=1];
for(int j=0;j<4;++j)
ins(x,y,x+dx[j],y+dy[j]);
printf("%d %d
",c6[1],c6[0]);
}
}