一道很好难写的并查集根号分治练习题。

定义 $n=R \cdot S$。

考虑并查集维护连通性，每次暴力合并，时间复杂度最劣会到 $O(n^2 \alpha(n))$。

考虑根号分治。邻居数 $< B$ 的小块的可以暴力合并邻居，$\ge B$ 的大块考虑使用 unordered_map 套 set 维护邻居颜色的块数：

unordered_map<int,set<int>>mp[B];
这里的 mp[i][j] 表示第 i 个大块的第 j 种颜色的邻居组成的集合。

一个块的颜色更改会引起周围相同颜色的块和它合并。具体可以这么实现：

• 首先更新周围的大块维护的邻居颜色；

• 然后把它和周围相同颜色的合并（小块：按照小块并到大块上、小块到达一定程度自动变成大块的方法；大块：相同颜色的直接合并，这样总共最多合并 $n$ 次。）。

考虑合并：

• 小块对小块

  暴力合并邻居即可。

  注意合并后的小块邻居数 $\ge B$ 就要变成大块。

  我的实现时间复杂度 $O(B\log n)$，小块变大块复杂度 $O(B \log n)$。

• 小块对大块

  小块的邻居加入大块上，复杂度 $O(B\log n)$。

• 大块对大块

  启发式合并，均摊复杂度 $O(n\log^2n)$。

合并完后更新并查集 $O(\alpha(n))$（我的实现 $O(\log n)$）。

注意由于并查集会让其中一块连到另外一块，所以每次合并完还要更新一遍它的所有大块邻居，复杂度 $\frac{n}{B}\log n$。

显然最多合并 $n$ 次，所以合并的复杂度是 $O(\frac{n^2}{B}\log n+nB\log n+n\log^2 n)$。

颜色更改的复杂度同理 $O(\frac{qn}B \log n+B \log n + n\log^2n)$。

所以总复杂度 $O(\frac{n^2}{B}\log n+nB\log n+n\log^2 n)$，取 $B= \sqrt n$ 最优，但是由于 $O(B \log n)$ 常数比较小，所以取 $B=2000$ 可以通过。

代码实现比较困难。

:::info[一种可能的实现]

#define F(a,f,e) for(int a=f;a<=e;++a)
const int N=8e5+5,B=1e5+5,bb=2005;
vector<vector<int>>mp,bel;
vector<int>near[N];
pair<int,int>zb[N];
unordered_map<int,set<int>>bignear[B];
int n,m,q,cnt,ys[N],bigcnt;
struct dsu{
	int fa[N],col[N],bcnt[N],bid[N],cnt,sz[N];
	inline int id(int x,int y){return x*m+y;}
	int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
	inline void add(int x,int y){
		x=find(x),y=find(y);
		if(x==y)return;
		sz[y]+=sz[x];
		fa[x]=y;
	}
	inline void csh(int n){for(int i=1;i<=n;++i)fa[i]=i;}
	inline void add(int x1,int y1,int x2,int y2){add(id(x1,y1),id(x2,y2));}
	inline void cgcol(int x,int y,int c){col[find(id(x,y))]=c;}
	inline int getcol(int x,int y){return col[find(id(x,y))];}
	inline void newid(int x,int y){int f=find(id(x,y));if(!bid[f])bid[f]=++cnt;}
	inline int getid(int x,int y){return bid[find(id(x,y))];}
	inline int getsz(int x,int y){return sz[find(id(x,y))];}
}b;
inline int getcol(int x){return b.getcol(zb[x].first,zb[x].second);}
inline int getsz(int x){return b.getsz(zb[x].first,zb[x].second);}
inline void add(int x,int y){b.add(zb[x].first,zb[x].second,zb[y].first,zb[y].second);}
inline int getid(int x){return b.getid(zb[x].first,zb[x].second);}
inline void cgcol(int x,int c){b.cgcol(zb[x].first,zb[x].second,c);}
inline void stb(int x){//small to big
	ys[x]=++bigcnt;
	assert(bigcnt<B);
	for(auto v:near[x]){
		v=getid(v);
		bignear[bigcnt][b.getcol(zb[v].first,zb[v].second)].insert(v);
	}
	near[x].clear();
}
inline void updatenear(int x,int newcol){
	int colx=getcol(x);
	for(auto v:near[x]){
		v=getid(v);
		if(ys[v]){
			auto it=bignear[ys[v]][colx].find(x);
			if(it!=bignear[ys[v]][colx].end())
				bignear[ys[v]][colx].erase(it),
				bignear[ys[v]][newcol].insert(getid(x));
		}
	}
}
inline void updatebignear(int x,int newcol){
	int colx=getcol(x);
	for(int i=1;i<=bigcnt;++i){
		auto it=bignear[i][colx].find(x);
		if(it!=bignear[i][colx].end())bignear[i][colx].erase(it),bignear[i][newcol].insert(getid(x));
	}
}
inline void updatebignear1(int x,int newcol,int y){
	int colx=newcol;
	for(int i=1;i<=bigcnt;++i){
		auto it=bignear[i][colx].find(x);
		if(it!=bignear[i][colx].end()){
			bignear[i][colx].insert(y);
		}
	}
}
inline void merge(int x,int y){
	if(x==y)return;
	if(!ys[x]&&!ys[y]){
		for(auto v:near[x])if(getid(v)!=y)near[y].push_back(getid(v));
		add(x,y);
		updatebignear1(x,getcol(y),y);
		sort(near[y].begin(),near[y].end());
		unique(near[y].begin(),near[y].end());
		if(near[y].size()>bb)stb(y);
		
		return;
	}
	if(ys[x]&&ys[y]){
		if(getsz(x)>getsz(y))swap(x,y);
		for(auto&vv:bignear[ys[x]])for(auto v:vv.second)if(getid(v)!=y)bignear[ys[y]][getcol(v)].insert(getid(v));
		add(x,y);
		updatebignear(x,getcol(y));
		return;
	}
	if(ys[x])swap(x,y);
	for(auto v:near[x])if(getid(v)!=y)bignear[ys[y]][getcol(v)].insert(getid(v));
	add(x,y);
	updatebignear1(x,getcol(y),y);
}
inline void cgcol2(int x,int newcol){
	if(ys[x]){
		updatebignear(x,newcol);
		cgcol(x,newcol);
		for(auto v:bignear[ys[x]][newcol])if(getcol(v)==newcol)merge(getid(x),getid(v));
		bignear[ys[x]][newcol].clear();
		return;
	}
	updatebignear(x,newcol);
	cgcol(x,newcol);
	for(auto v:near[x])if(getcol(v)==newcol)merge(getid(x),getid(v));
}
inline void work(){
	cin>>n>>m;
	b.csh(2*(n+1)*(m)+2);
	mp.resize(n+2),bel.resize(n+2);
	F(i,0,n+1){mp[i].resize(m+2),bel[i].resize(m+2);F(j,0,m+1)mp[i][j]=-1;}
	F(i,1,n)F(j,1,m)cin>>mp[i][j];
	F(i,1,n)F(j,1,m){
		if(mp[i][j]==mp[i+1][j])b.add(i,j,i+1,j);
		if(mp[i][j]==mp[i-1][j])b.add(i,j,i-1,j);
		if(mp[i][j]==mp[i][j-1])b.add(i,j,i,j-1);
		if(mp[i][j]==mp[i][j+1])b.add(i,j,i,j+1);
	}
	F(i,1,n)F(j,1,m)b.newid(i,j);
	F(i,1,n)F(j,1,m){
		if(mp[i+1][j]!=-1&&mp[i][j]!=mp[i+1][j])near[b.getid(i,j)].push_back(b.getid(i+1,j));
		if(mp[i-1][j]!=-1&&mp[i][j]!=mp[i-1][j])near[b.getid(i,j)].push_back(b.getid(i-1,j));
		if(mp[i][j+1]!=-1&&mp[i][j]!=mp[i][j+1])near[b.getid(i,j)].push_back(b.getid(i,j+1));
		if(mp[i][j-1]!=-1&&mp[i][j]!=mp[i][j-1])near[b.getid(i,j)].push_back(b.getid(i,j-1));
		int id=b.getid(i,j);
		zb[id]=make_pair(i,j);
	}
	F(i,1,b.cnt){
		cgcol(i,mp[zb[i].first][zb[i].second]);
		sort(near[i].begin(),near[i].end());
		near[i].resize(unique(near[i].begin(),near[i].end())-near[i].begin());
	}
	F(i,1,b.cnt)if(near[i].size()>=bb)stb(i);
	cin>>q;
	F(i,1,q){
		int r,s,c;
		cin>>r>>s>>c;
		int id=b.getid(r,s);
		cgcol2(id,c);
	}
	F(i,1,n){F(j,1,m)cout<<b.getcol(i,j)<<' ';cout<<'\n';}
}

:::

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e5+5,K=255;
int n,m,q,B,c[N],fa[N],id[N],siz[N],cnt,p[N];
basic_string<int>v[N];
unordered_map< int,vector<int> >w[K];
bitset<K>s[N];
int find(int x)
{
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void build(int x)
{
	id[x]=++cnt;
	for(auto y:v[x])y=find(y),w[cnt][c[y]].push_back(y),s[x][id[y]]=1,s[y][cnt]=1;
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y)return;
	if(siz[x]<siz[y])swap(x,y);
	fa[y]=x;
	if(siz[x]>B)
	{
		for(auto z:v[y])
		{
			z=find(z);
			if((z^x)&&(z^y))w[id[x]][c[z]].push_back(z),v[x].push_back(z),s[x][id[z]]=1,s[z][id[x]]=1;
		}
	}
	else
	{
		for(auto z:v[y])
		{
			z=find(z);
			if((z^x)&&(z^y))v[x].push_back(z),s[x][id[z]]=1;
		}
		if(siz[x]+siz[y]>B)build(x);
	}
	siz[x]+=siz[y];
	return;
}
signed main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",c+(i-1)*m+j);
	for(int i=1;i<=n*m;i++)fa[i]=i,siz[i]=1;
	B=2*sqrt(n*m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int x=(i-1)*m+j;
			if(i>1)v[x].push_back(x-m);
			if(j>1)v[x].push_back(x-1);
			if(i<n)v[x].push_back(x+m);
			if(j<m)v[x].push_back(x+1);
		}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			int x=(i-1)*m+j;
			if(i>1&&c[x]==c[x-m])merge(x,x-m);
			if(j>1&&c[x]==c[x-1])merge(x,x-1);
			if(i<n&&c[x]==c[x+m])merge(x,x+m);
			if(j<m&&c[x]==c[x+1])merge(x,x+1);
		}
	int mx=0;
	for(int i=1;i<=n*m;i++)mx=max(mx,(int)v[i].size());
	scanf("%d",&q);
	while(q--)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		x=find((x-1)*m+y),y=z;
		if(c[x]==y)continue;
		c[x]=y;
		for(int i=1;i<=cnt;i++)if(s[x][i])w[i][c[x]].push_back(x);
		if(siz[x]<=B)
		{
			int cnt=0;
			for(auto y:v[x])if(find(y)!=x)p[++cnt]=y;
			v[x].clear();
			for(int i=1;i<=cnt;i++)v[x].push_back(p[i]);
			for(int i=1;i<=cnt;i++)if(c[x]==c[find(p[i])])merge(x,p[i]);
		}
		else
		{
			int cnt=0;
			for(auto y:w[id[x]][c[x]])if(find(y)!=x&&c[find(y)]==c[x])p[++cnt]=y;
			w[id[x]][c[x]].clear();
			for(int i=1;i<=cnt;i++)merge(x,p[i]);
		}
	}
	for(int i=1;i<=n;i++,putchar('\n'))for(int j=1;j<=m;j++)printf("%d ",c[find((i-1)*m+j)]);
	return 0;
}