自动搬运

查看原文

来自洛谷，原作者为

	iyaang 不因过往而自卑

搬运于2025-08-24 21:56:42，当前版本为作者最后更新于2022-07-19 15:31:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

【WC2005】双面棋盘

题目链接

这天做双面棋盘这道题，发现题解里面大多都是 LCT ，对于线段树套并查集的写法思路讲评很少而且不大清晰，因此有了这一篇题解。

维护联通块的数量，很容易联想到使用并查集，考虑暴力，用并查集记录每个点的连通性，最后统计块数即可。但是如果每次进行格子翻转的操作都暴力重构并查集，时间复杂度达到 $O(N^2M)$ ，无法忍受。

不考虑翻转操作，思考从小一点的数据入手，假设这个棋盘只有一行，如：

0 0 1 1 0 0 

容易得出这一行有两个白色联通块，一个黑色联通块。

将棋盘情况扩展到两行，如：

0 0 1 1 0 0
0 1 1 1 0 0

对于第二行，也是两个白色联通块，一个黑色联通块，但是当上下两行连起来时，总数依旧为两个白色联通块，一个黑色联通块。先假设上下两行的联通块个数不互相影响，即总共有四个白色联通块，两个黑色联通块。当第一列相接时，颜色相同，会减少一个白色联通块；当第三列相接时，颜色相同，会减少一个黑色联通块；当第四列相接时，由于 $(1,3)$ 和 $(1,4)$ 联通， $(2,3)$ 和 $(2,4)$ 联通， 刚刚第三列相接标记了 $(1,3)$ 和 $(2,3)$ 联通，所以在并查集中 $(1,4)$ 和 $(2,4)$ 也是联通的，因此块数并不会减少。以此类推。

这时我们可以得出结论：每一行的联通块个数在拼接时并不会改变，多行的联通块个数由相邻的两行的联通块个数和每一列上相邻两格的颜色决定。

因此我们可以以行为单位，维护好区间联通块个数以及最上面一行和最下面一行的连通性信息（叶子节点二者都是它本身）。因为在相接时只有这两行会对最终联通块个数产生影响。

考虑线段树，在叶子节点维护每一行的联通块个数，然后合并每一行，类推到大的区间，最后直接取出线段树结构体中 $1$ 号节点（即整个棋盘）的联通块个数即可。

行与行合并时进行 pushup 操作，直接暴力合并，遍历一遍每一列是否是同一颜色即可。

对于翻转操作，相当于单点修改，我们直接重构这一行的并查集和叶子节点信息，然后同样向上 pushup ，与建树的操作是类似的，因此写代码的时候可以直接对称着写。

时间复杂度 $O(N^2+MN \log^2 N)$。

因为维护的是行的信息，所以代码中的“左”表示“上”，“右”表示“下”。

代码中有更为详细的解释。

个人感觉码风很好？

#include<bits/stdc++.h>
#define MAX 210
using namespace std;

inline int read()
{
    int s=0,w=1;
    char c=getchar();
    while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
    while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
    return s*w;
}

int n,m,x,y;
int g[MAX][MAX];  //存棋盘

//并查集，二维压成一维
int fa[MAX*MAX];    
inline int get(int i,int j)   //计算在并查集中的编号 
{
	return (i-1)*n+j;
} 
inline int find(int x)
{
	if(x==fa[x]) return x;
	return fa[x]=find(fa[x]);
} 

//线段树  0为白色   1为黑色
struct Segment_tree
{
	int white,black;   //维护当前这几行的黑白联通块数量
	int l,r;        //维护当前这几行的最上边和最下边的行是什么 
	int ls[MAX],rs[MAX];   //维护当前这几行的最上面一行和最下面一行的连通性（即父节点） 
}t[MAX*4];
inline void pushup(int i)   //暴力合并、父节点更新 
{
	for(int j=1;j<=n;j++)
	{
		//父亲节点的最上行是他左（上）儿子的最上行，父亲节点的最下行是他右（下）儿子的最下行 
		t[i].ls[j]=t[i<<1].ls[j];
		t[i].rs[j]=t[i<<1|1].rs[j];
		//重新计算联通块信息，初始化已经记录下了编号所以不用再get 
		fa[t[i<<1].ls[j]]=t[i<<1].ls[j];
		fa[t[i<<1].rs[j]]=t[i<<1].rs[j];
		fa[t[i<<1|1].ls[j]]=t[i<<1|1].ls[j];
		fa[t[i<<1|1].rs[j]]=t[i<<1|1].rs[j];
	}
	//先假设没有合并，然后再一点点减去 
	t[i].black=t[i<<1].black+t[i<<1|1].black;
	t[i].white=t[i<<1].white+t[i<<1|1].white;
	int mid=(t[i].l+t[i].r)>>1;  //寻找交界的部分 
	for(int j=1;j<=n;j++)
		if(g[mid][j]==g[mid+1][j])   //如果是同一种颜色就要进行合并操作
		{
		//相交的部分为左（上）儿子的最下端和右（下）儿子的最上端 
			int l=find(t[i<<1].rs[j]);   
			int r=find(t[i<<1|1].ls[j]);   
			if(l!=r)
			{
				fa[l]=r;
				if(g[mid][j]==0&&g[mid+1][j]==0) t[i].white--;
				if(g[mid][j]==1&&g[mid+1][j]==1) t[i].black--;
			}
		}
	//更新根节点的信息，一定要让边上为根节点 
	for(int j=1;j<=n;j++)
		t[i].ls[j]=find(t[i].ls[j]),t[i].rs[j]=find(t[i].rs[j]);
}
inline void build(int i,int l,int r)   //建树 
{
	t[i].l=l,t[i].r=r;
	if(l==r)   
	{
		for(int j=1;j<=n;j++)    //初始每一行的每一个点的父亲都是他自己，假设每一个格子都是单独的联通块 
		{
			t[i].ls[j]=t[i].rs[j]=fa[get(l,j)]=get(l,j);
			if(g[l][j]==0) t[i].white++;
			else t[i].black++;
		}
		for(int j=2;j<=n;j++)  //统计这一行的黑白联通块个数，去掉重复计算的联通块 
			if(g[l][j]==g[l][j-1])
			{
				t[i].ls[j]=t[i].rs[j]=fa[get(l,j)]=fa[get(l,j-1)];   //注意是连接到父亲！！！ 
				if(g[l][j]==0) t[i].white--;
				else t[i].black--;
			}
		return;
	}
	int mid=(l+r)>>1;
	build(i<<1,l,mid);
	build(i<<1|1,mid+1,r);
	pushup(i);
	return;
}
inline void change(int i,int to)    //单行修改
{
	if(t[i].l==t[i].r)
	{
		t[i].white=t[i].black=0;   //暴力重新计算，注意清零，剩下的操作与建树是一样的 
		for(int j=1;j<=n;j++)  
		{
			t[i].ls[j]=t[i].rs[j]=fa[get(to,j)]=get(to,j);
			if(g[t[i].l][j]==0) t[i].white++;
			else t[i].black++;
		}
		for(int j=2;j<=n;j++)
			if(g[t[i].l][j]==g[t[i].l][j-1])
			{
				t[i].ls[j]=t[i].rs[j]=fa[get(to,j)]=fa[get(to,j-1)];
				if(g[t[i].l][j]==0) t[i].white--;
				else t[i].black--;
			}
		return;
	}
	if(t[i<<1].r>=to) change(i<<1,to); 
	if(t[i<<1|1].l<=to) change(i<<1|1,to);
	pushup(i);
	return;
}

int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			g[i][j]=read();
	build(1,1,n);
	m=read();
	for(int i=1;i<=m;i++)
	{
		x=read(),y=read();
		g[x][y]=(g[x][y]==0)?1:0;
		change(1,x);
		printf("%d %d\n",t[1].black,t[1].white);
	}
	return 0;
}

updata 2022.8.5 感谢@老子是北瓜，修改了错误的时间复杂度。