自动搬运

查看原文

来自洛谷，原作者为

	Lynkcat Reset.

搬运于2025-08-24 22:38:57，当前版本为作者最后更新于2022-07-06 19:46:49，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

终于传上来了，咕咕了两年了属实不容易。

考虑一个很裸的暴力，我们每次 BFS 然后更新染色。时间复杂度显然很劣。

接下来我们考虑根号分治。（下面称相邻的连通块为邻居）

考虑面积 $\leq B$ 的块，我们可以暴力扫描它的邻居然后合并。

考虑面积 $>B$ 的块，我们称之为大块，我们对于所有大块去维护一个哈希表，$f(x)$ 表示这个大块颜色为 $x$ 的所有邻居集合，由于大块个数最多只有 $\frac{n}{B}$ ，所以这里空间复杂度上界为 $O(\frac{n^2}{B})$（实际常数很小）。

为了支持这个哈希表的更新，我们还必须对于所有块去维护其邻居中大块的集合，所以这里空间复杂度上界同 $O(\frac{n^2}{B})$（实际常数很小）。

再考虑两个块的合并，我们采用启发式合并，每次将小的集合连向大的集合。

由于每个连通块的合并次数不会超过 $\log$ 次，每次小块寻找邻居的复杂度最多为 $B$ 级别的，大块寻找邻居是 $O(\frac{R\times S}{B})$ 级别的， 所以复杂度大约是 $O(R\times S\times \log(R\times S)+Q\times B+\frac{Q\times R\times S}{B})$。即 $O(n\sqrt n)$ 级别的。

实现时细节还是很多的。自己注意下别写错复杂度就行。

//QwQcOrZ yyds!!!
#include<bits/stdc++.h>
#define ll long long
#define F(i,a,b) for (int i=(a);i<=(b);++i)
#define R(i,a,b) for (int i=(a);i<(b);++i)
#define D(i,a,b) for (int i=(a);i>=(b);i--)
#define go(i,x) for (int i=head[x];i;i=e[i].nx)
#define mp make_pair
#define pb push_back
#define pa pair < int,int >
#define fi first
#define se second
#define re register
#define be begin()
#define en end()
#define sqr(x) ((x)*(x))
#define ret return puts("-1"),0;
#define put putchar('\n')
#define inf 1000000005
#define mod 998244353
//#define int ll
#define N 200005
using namespace std;
inline char gc(){static char buf[100000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}
//#define gc getchar
inline ll read(){char c=gc();ll su=0,f=1;for (;c<'0'||c>'9';c=gc()) if (c=='-') f=-1;for (;c>='0'&&c<='9';c=gc()) su=su*10+c-'0';return su*f;}
inline void write(ll x){if (x<0){putchar('-');write(-x);return;}if (x>=10) write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x),putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
int n,m,Q,fa[N],neg[N],xx,yy,col,ID,cnt;
const int c[]={0,0,0,-1,1},d[]={0,-1,1,0,0};
const int B=0;
vector<vector<int> >a,bel;
struct
{
	int large,col;
	vector<pa>nod;
	vector<int>bignb;
	map<int,vector<int>>lis;
}S[N];
int gf(int x)
{
	if (x==fa[x]) return x;
	return gf(fa[x]);
}
void dfs(int x,int y)
{
	S[cnt].nod.push_back({x,y});
	bel[x][y]=cnt;
	for (int i=1;i<=4;++i)
	{
		int u=x+c[i],v=y+d[i];
		if (u>=1&&u<=n&&v>=1&&v<=m)
		{
			if (a[u][v]==a[x][y]&&!bel[u][v])
			{
				dfs(u,v);
			}
		}
	}
}
inline void turn_to_big(int now)
{
	S[now].large=1;
	vector<int>nowb;
	ID++;
	for (auto u:S[now].nod)
	{
		for (int j=1;j<=4;++j)
		{
			int x=u.fi+c[j],y=u.se+d[j];
			if (x>=1&&x<=n&&y>=1&&y<=m)
			{
				if (bel[x][y]==now) continue;
				int v=bel[x][y];
				if (neg[v]==ID) continue;
				neg[v]=ID;
				S[v].bignb.push_back(now);
				S[now].lis[S[v].col].push_back(v);
			}
		}
	}
}
inline int merge(int x,int y)
{
	if (!S[x].large&&S[y].large) turn_to_big(x);
	else
	if (S[x].large&&!S[y].large) turn_to_big(y);
	
	if (S[x].nod.size()>S[y].nod.size()) swap(x,y);
	fa[x]=y;
	for (auto u:S[x].nod)
	{
		bel[u.fi][u.se]=y;
		S[y].nod.push_back(u);
	}
	vector<pa>().swap(S[x].nod);
	
	if (S[x].bignb.size()>S[y].bignb.size()) 
		S[x].bignb.swap(S[y].bignb);
	for (auto u:S[x].bignb)
	{
		S[y].bignb.push_back(u);
	}
	vector<int>().swap(S[x].bignb);
	re vector<int>nownb;
	ID++;
	for (auto u:S[y].bignb)
	{
		int uu=gf(u);
		if (uu!=y&&neg[uu]!=ID)
		{
			neg[uu]=ID;
			nownb.push_back(uu);
		}
	}
	vector<int>().swap(S[y].bignb);
	S[y].bignb=nownb;
	for (auto u:S[x].lis)
	{
		int nowcol=u.fi;
		auto &lis1=u.se;
		auto &lis2=S[y].lis[nowcol];
		if (lis1.size()>lis2.size()) lis1.swap(lis2);
		for (auto v:lis1)
		{
			lis2.push_back(v);
		}
		vector<int>().swap(lis1);
	}
	S[x].lis.clear();
	if (!S[y].large&&S[y].nod.size()>B) turn_to_big(y);
	return y;
}
signed main()
{
	n=read(),m=read();
	a.resize(n+10);
	for (re int i=1;i<=n;++i) a[i].resize(m+10);
	bel.resize(n+10);
	for (re int i=1;i<=n;++i) bel[i].resize(m+10);
	for (re int i=1;i<=n;++i)
		for (re int j=1;j<=m;++j)
			a[i][j]=read();
	for (re int i=1;i<=n;++i)
		for (re int j=1;j<=m;++j)
			if (!bel[i][j]) 
			{
				bel[i][j]=++cnt;
				S[cnt].large=0;
				S[cnt].nod.clear();
				S[cnt].bignb.clear();
				S[cnt].lis.clear();
				S[cnt].col=a[i][j];
				dfs(i,j);
			}
	for (re int i=1;i<=cnt;++i)
	{
		ID++;
		for (auto u:S[i].nod)
		{
			for (re int j=1;j<=4;++j)
			{
				int x=u.fi+c[j],y=u.se+d[j];
				if (x>=1&&x<=n&&y>=1&&y<=m)
				{
					if (bel[x][y]==i) continue;
					int v=bel[x][y];
					if (neg[v]==ID) continue;
					neg[v]=ID;
					if (S[v].nod.size()>B) S[i].bignb.push_back(v);
					if (S[i].nod.size()>B)
						S[i].lis[S[v].col].push_back(v);
				}
			}
		}
	}
	for (re int i=1;i<=cnt;++i)
	{
		if (S[i].nod.size()>B) turn_to_big(i);
		fa[i]=i;
	}
//	return 0;
	Q=read();
	while (Q--)
	{
		xx=read(),yy=read(),col=read();
		re int now=bel[xx][yy];
//		cout<<now<<" "<<S[now].large<<endl;
		if (!S[now].large)
		{
			re vector<int>nowb;
			ID++;
			for (auto u:S[now].nod)
			{
				for (re int j=1;j<=4;++j)
				{
					int x=u.fi+c[j],y=u.se+d[j];
					if (x>=1&&x<=n&&y>=1&&y<=m)
					{
						if (bel[x][y]==now) continue;
						int v=bel[x][y];
						if (neg[v]==ID) continue;
						neg[v]=ID;
						if (S[v].col==col) nowb.push_back(v);
					}
				}
			}
			for (auto u:nowb)
			{
				now=merge(now,u);
			}
			
			nowb.clear();
			ID++;
			for (auto u:S[now].bignb)
			{
				int uu=gf(u);
				if (uu!=now&&neg[uu]!=ID)
				{
					neg[uu]=ID;
					nowb.push_back(uu);
				}
			}
			S[now].bignb.clear();
			S[now].bignb=nowb;
			S[now].col=col;
			for (auto u:S[now].bignb)
			{
				S[u].lis[S[now].col].push_back(now);
			}
		}
		else
		{
			re vector<int>nowb;
			++ID;
			for (auto u:S[now].lis[col])
			{
				int uu=gf(u);
				if (uu!=now&&neg[uu]!=ID)
				{
					neg[uu]=ID;
					if (S[uu].col==col) nowb.push_back(uu);
				}
			}
			S[now].lis[col].clear();
			S[now].lis[col]=nowb;
//			cout<<"!"<<endl;
			for (auto u:nowb)
			{
//				cout<<u<<endl;
				now=merge(now,u);
			}
			nowb.clear();
			ID++;
			for (auto u:S[now].bignb)
			{
				int uu=gf(u);
				if (uu!=now&&neg[uu]!=ID)
				{
					neg[uu]=ID;
					nowb.push_back(uu);
				}
			}
			S[now].bignb.clear();
			S[now].bignb.swap(nowb);
				
			S[now].col=col;
			for (auto u:S[now].bignb)
			{
				S[u].lis[S[now].col].push_back(now);
			}
		}
	}
	for (re int i=1;i<=n;++i)
	{
		for (re int j=1;j<=m;++j)
			writesp(S[bel[i][j]].col);
		puts("");
	}
}