#C231107A. 剪发(haircut)

标签（Label）

并查集

前言（Front talk)

此题打了好久，我觉得做题前应该首先想好思路，然后想好实现方式，不能抓着半截就开打，否则只会花费更多的时间，总结下来就是：

What - 什么：想好思路；
Why - 为什么： 想好细节；
How - 怎么做：想好做法；

其实只花费了最多 $20min$ 就想出来了这道题，但是因为自己的代码太难看，并查集合并都打了很久，花了整整两个小时…( ＿＿)ノ｜ 。

网址（Website）

题目详情 - 剪发(haircut) - Super

题解 - 剪发(haircut) - Super

题解（Solution）

~~$\qquad$因为正向不好想，所以我们可以倒着来。~~

$\qquad$反正我再也不想听到有人讲题这样讲了。

$\qquad$所以，我们来想一下这道题为什么不能正着做：

$\qquad$首先，每次将一格删去，我们都需要判断一下有没有将某个连通块拆掉，则需要申请一个新的位置来储存这个新的区块，而且，判断有没有拆掉可能还需要对当前连通块判环，如果有环，肯定是拆不掉的，如果每次都跑一次 $tarjan$ 时间复杂度将达到惊人的 $O(nmq)$ ，你有可能用两个小时都打不出一个暴力分。

$\qquad$拆分当然是可以转换为合并的，因此，我们将每一个询问离线，倒着加头发，用并查集维护一下连通块数量和最大的 $size$ 就可以轻易的解决此题。

代码（Code）

#include<bits/stdc++.h>
#include<map>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int> 
#define Fi first
#define Se second
inline int input(){char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;}
const int Q = 3012345;
const int N = 3005;
bool ST;
bitset<N> a[N];
int n,m,q,maxs,num;
int x[Q],y[Q];
P ans[Q];

P fa[N][N];//二维并查集 
inline P find(P p){
	int x=p.Fi,y=p.Se;
	if(fa[x][y]==make_pair(x,y)) return {x,y};
	return fa[x][y]=find(fa[x][y]);
}

int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int siz[N][N];
map<P,int> mp;
bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	string str("haircut");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	int T=input();
	while(T--){
		n=input(),m=input(),q=input();
		For(i,1,n) For(j,1,m) a[i][j]=(input()==true),fa[i][j]={i,j},siz[i][j]=1;
		For(i,1,q) x[i]=input(),y[i]=input(),a[x[i]][y[i]]=false;
		For(i,1,n) For(j,1,m) if(a[i][j]){
			For(k,0,3){
				int tx=i+dx[k],ty=j+dy[k];
				if(tx<=0 || tx>n || ty<=0 || ty>m) continue;
				if(a[tx][ty]){
					P fx=find({tx,ty}),fy=find({i,j});
					if(fx==fy) continue;
					fa[fx.Fi][fx.Se]=fy;
					siz[fy.Fi][fy.Se]+=siz[fx.Fi][fx.Se];
					maxs=max(maxs,siz[fy.Fi][fy.Se]);
				}
			}
		}
		For(i,1,n) For(j,1,m) if(a[i][j]){P f=find({i,j});mp[f]++;}
		num=mp.size();
		Rof(i,q,1){
			a[x[i]][y[i]]=true;
			ans[i]={num,maxs};
			For(k,0,3){
				int tx=x[i]+dx[k],ty=y[i]+dy[k];
				if(tx<=0 || tx>n || ty<=0 || ty>m) continue;
				if(a[tx][ty]){
					P fx=find({tx,ty}),fy=find({x[i],y[i]});
					if(fx==fy) continue;
					fa[fx.Fi][fx.Se]=fy;num--;
					siz[fy.Fi][fy.Se]+=siz[fx.Fi][fx.Se];
					maxs=max(maxs,siz[fy.Fi][fy.Se]);
				}
			}if(fa[x[i]][y[i]]==make_pair(x[i],y[i])) num++,maxs=max(1,maxs);
		}For(i,1,q) printf("%d %d\n",ans[i].Fi,ans[i].Se);
		
		maxs=0;mp.clear();
	}return 0;
}