记录编号	440290	评测结果	AAAAAAAAAA
题目名称	双面棋盘	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.852 s
提交时间	2017-08-22 21:10:56	内存使用	8.49 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=210,M=4e5+10;
struct edge{int l,r,u,v,color;};
vector<edge> V;
bool query[M];
int ansb[M],answ[M],fa[M],idx[M];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void solve(int l,int r,int n,int nb,int nw,vector<edge> v){
	for (int i=1;i<=n;i++) fa[i]=i;
	for (int i=0;i<v.size();i++){
		edge now=v[i];
		if (now.l<=l&&now.r>=r){
			int a=find(now.u),b=find(now.v);
			if (a!=b) fa[a]=b,now.color?nb++:nw++;
		}
	}
	int m=0;
	for (int i=1;i<=n;i++)
		if (i==fa[i]) idx[i]=++m;
	for (int i=0;i<v.size();i++){
		v[i].u=idx[find(v[i].u)];
		v[i].v=idx[find(v[i].v)];
	}
	for (int i=1;i<=n;i++) idx[i]=0;
	if (l==r){
		ansb[l]-=nb;
		answ[l]-=nw;
		return;
	}
	int mid=(l+r)>>1;
	vector<edge> vl,vr;
	for (int i=0;i<v.size();i++){
		edge now=v[i];
		if (now.u==now.v) continue;
		if (now.l<=l&&now.r>=r) continue;
		if (now.l<=mid) vl.push_back(now);
		if (now.r>mid) vr.push_back(now);
	}
	solve(l,mid,m,nb,nw,vl);solve(mid+1,r,m,nb,nw,vr);
}
int n,m,cnt,id[N][N],color[M];
const int fx[4]={1,-1,0,0},fy[4]={0,0,1,-1};
typedef pair<int,int> pii;
map<pii,int> mp;
int nb,nw;
int main()
{
	freopen("dface.in","r",stdin);
	freopen("dface.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	for (int j=1;j<=n;j++){
		id[i][j]=++cnt;
		scanf("%d",&color[id[i][j]]);
		if (color[id[i][j]]) nb++;else nw++;
		if (i>1&&color[id[i][j]]==color[id[i-1][j]])
			mp[pii(id[i][j],id[i-1][j])]=mp[pii(id[i-1][j],id[i][j])]=0;
		if (j>1&&color[id[i][j]]==color[id[i][j-1]])
			mp[pii(id[i][j],id[i][j-1])]=mp[pii(id[i][j-1],id[i][j])]=0;
	}
	ansb[0]=nb;answ[0]=nw;
	scanf("%d",&m);
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		int u=id[x][y];
		for (int k=0;k<4;k++){
			int a=x+fx[k],b=y+fy[k];
			if (!(a&&a<=n&&b&&b<=n)) continue;
			int v=id[a][b];
			if (color[u]==color[v]){
				V.push_back((edge){mp[pii(u,v)],i-1,u,v,color[u]});
				mp.erase(pii(u,v));
				mp.erase(pii(v,u));
			}
			else mp[pii(u,v)]=mp[pii(v,u)]=i;
		}
		color[u]?(nb--,nw++):(nb++,nw--);
		color[u]^=1;
		ansb[i]=nb;answ[i]=nw;
	}
	for (map<pii,int>::iterator i=mp.begin();i!=mp.end();++i){
		int u=(i->first).first,v=(i->first).second;
		V.push_back((edge){i->second,m,u,v,color[u]});
	}
	/*for (int i=0;i<V.size();i++){
		edge now=V[i];
		printf("[%d,%d] %d<->%d color=%d\n",now.l,now.r,now.u,now.v,now.color);
	}*/
	solve(0,m,n*n,0,0,V);
	for (int i=1;i<=m;i++) printf("%d %d\n",ansb[i],answ[i]);
	return 0;
}