[BZOJ1453]Dface双面棋盘

Description
Input
Output
Sample Input
Sample Output
HINT
线段树+并查集，暴力记录和更新一些信息，详情见代码注解。
#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)     print(x/10);

	putchar(x%10+'0');

}

const int N=2e2;

int map[N+10][N+10];

int ID[N*4+10],fa[N*4+10];

int n,m;

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}

struct Segment{

	#define ls (p<<1)

	#define rs (p<<1|1)

	struct AC{//线段树记录列数，struct内存储一个列区间的信息

		int lcnt[N+10],rcnt[N+10];	//记录最左列和最右列每行所属联通块编号，如BBWWBB编号为1,1,2,2,3,3

		int W,B,T;	//记录白块(W)，黑块(B)个数，T为lcnt[n]+rcnt[n]

		int l,r;

		void clear(){

			l=r=W=B=T=0;

			memset(lcnt,0,sizeof(lcnt));

			memset(rcnt,0,sizeof(rcnt));

		}

		void init(int x){//单点暴力

			B=W=0;

			for (int i=1;i<=n;i++){

				if (i==1||map[i][x]!=map[i-1][x])	map[i][x]?B++:W++;

				lcnt[i]=rcnt[i]=B+W;

			}

			T=B+W;

		}

	}tree[N*4+10];

	friend AC operator +(const AC &x,const AC &y){

		AC z; z.clear();

		z.l=x.l,z.r=y.r;

		z.B=x.B+y.B;

		z.W=x.W+y.W;

		for (int i=1;i<=x.T+y.T;i++)	fa[i]=i,ID[i]=0;	//T的用处（优化）

		for (int i=1,p1,p2;i<=n;i++){//把y的信息加上x.T,使它们为一个图

			if (map[i][x.r]!=map[i][y.l])	continue;

			if ((p1=find(x.rcnt[i]))!=(p2=find(y.lcnt[i]+x.T))){

				fa[p2]=p1;	//记得连向小的标号……

				map[i][x.r]?z.B--:z.W--;

			}

		}

		int Rank=0;

		for (int i=1;i<=n;i++){//离散化

			int p1=find(x.lcnt[i]),p2=find(y.rcnt[i]+x.T);

			if (!ID[p1])	ID[p1]=++Rank;

			if (!ID[p2])	ID[p2]=++Rank;

			z.lcnt[i]=ID[p1];

			z.rcnt[i]=ID[p2];

		}

		z.T=Rank;

		return z;

	}

	void build(int p,int l,int r){

		tree[p].l=l,tree[p].r=r;

		if (l==r){

			tree[p].init(l);

			return;

		}

		int mid=(l+r)>>1;

		build(ls,l,mid),build(rs,mid+1,r);

		tree[p]=tree[ls]+tree[rs];

	}

	void change(int p,int l,int r,int x){

		if (l==r){

			tree[p].init(l);

			return;

		}

		int mid=(l+r)>>1;

		if (x<=mid)	change(ls,l,mid,x);

		if (x>mid)	change(rs,mid+1,r,x);

		tree[p]=tree[ls]+tree[rs];

	}

	void work(){

		int x=read(),y=read();

		map[x][y]^=1;

		change(1,1,n,y);

		printf("%d %d\n",tree[1].B,tree[1].W);

	}

}T;

int main(){

	n=read();

	for (int i=1;i<=n;i++)	for (int j=1;j<=n;j++)	map[i][j]=read();

	T.build(1,1,n);

	m=read();

	for (int i=1;i<=m;i++)	T.work();

	return 0;

}
巴特西

[BZOJ1453]Dface双面棋盘

最新文章

热门文章
