在sub2中，我们使用并查集维护每一个颜色相同连续段。
在并查集的根部存储当前的颜色和连续段的左/右端点。
每次尝试拓展一下。
在sub3中，根据sub2的启发，我们也维护连通块使得相邻的连通块颜色不同。
在修改时，如果我们成功把当前点修改成另一个颜色，则当前点的所有相邻点都会和这个点合并。
维护一个点的所有相邻点可以启发式合并。
注意到如果我们对一个连通块\(x\)的所有连向的连通块\(y\)进行合并，则\(x->y\)的边都没用了，可以被删除。
这个删除操作保证了时间复杂度，使每条边只会被遍历1次。
时间复杂度\(RS\log_2{RS}\)。
48分代码（没调完）

#include<bits/stdc++.h>
using namespace std;
#define N 200010
int a,b,l[N],r[N],v[N],p[N],q,t[N],c[N],tx[4]={1,0,-1,0},ty[4]={0,-1,0,1},tp,vi[N];
int fd(int x){
	return !p[x]?x:p[x]=fd(p[x]); 
}
int id(int x,int y){
	return (x-1)*b+y;
}
struct no{
	int x,y;
}st[N];
queue<no>qu;
unordered_map<int,int>ma[N];
void mg(unordered_map<int,int> &x,unordered_map<int,int> &y){
	if(x.size()<y.size())
		swap(x,y);
	for(unordered_map<int,int>::iterator it=x.begin();it!=x.end();it++){
		int a=it->first,b=it->second;
		x[a]+=b;
	}
	y.clear();
}
int main(){
	//freopen("r.in","r",stdin);
	scanf("%d%d",&a,&b);
	if(a==1){
		for(int i=1;i<=b;i++)
			scanf("%d",&v[i]);
		int j=1;
		for(int i=1;i<=b;){
			j=i;
			while(j<b&&v[i]==v[j+1])
				j++;
			for(int k=i;k<=j;k++){
				int xx=fd(i),yy=fd(k);
				if(xx!=yy)
					p[xx]=yy;
			}
			l[fd(i)]=i;
			r[fd(i)]=j;
			t[fd(i)]=v[i];
			i=j+1;
		}
		scanf("%d",&q);
		while(q--){
			int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			t[fd(y)]=c;
			while(1){
				int g=fd(y),e=l[g],f=r[g],ok=0;
				if(e>1&&t[fd(e-1)]==t[g]){
					int yy=fd(e-1);
					p[yy]=g;
					l[g]=l[yy];
					ok=1;
				}
				if(f<b&&t[fd(f+1)]==t[g]){
					int yy=fd(f+1);
					p[yy]=g;
					r[g]=r[yy];
					ok=1;
				}
				if(!ok)
					break;
			}
		}
		for(int i=1;i<=b;i++)
			printf("%d ",t[fd(i)]);
		return 0;
	}
	if(a*b<=10000){
		for(int i=1;i<=a;i++)
			for(int j=1;j<=b;j++)
				scanf("%d",&c[id(i,j)]);
		int q,ct=0;
		scanf("%d",&q);
		while(q--){
			int x,y,z;
			scanf("%d%d%d",&x,&y,&z);
			qu.push((no){x,y});
			while(!qu.empty()){
				no x=qu.front();
				qu.pop();
				st[++tp]=x;
				int e=x.x,f=x.y;
				vi[id(e,f)]=1;
				for(int i=0;i<4;i++){
					int dx=e+tx[i],dy=f+ty[i];
					if(dx<1||dx>a||dy<1||dy>b)
						continue;
					if(!vi[id(dx,dy)]&&c[id(dx,dy)]==c[id(e,f)]){
						qu.push((no){dx,dy});
						vi[id(dx,dy)]=1;
					}
				}
			}
			for(int i=1;i<=tp;i++){
				c[id(st[i].x,st[i].y)]=z;
				vi[id(st[i].x,st[i].y)]=0;
			}
			tp=0;
		}
		for(int i=1;i<=a;i++){
			for(int j=1;j<=b;j++)
				printf("%d ",c[id(i,j)]);
			puts("");
		}
		return 0;
	}
	int ok=1;
	for(int i=1;i<=a;i++)
		for(int j=1;j<=b;j++){
			scanf("%d",&c[id(i,j)]);
			if(c[id(i,j)]!=1&&c[id(i,j)]!=0)
				ok=0;
		}
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d%d",&l[i],&r[i],&v[i]);
		if(v[i]!=1&&v[i]!=0)
			ok=0;
	}
	if(ok){
		for(int i=1;i<=a;i++)
			for(int j=1;j<=b;j++)
				for(int d=0;d<4;d++){
					int dx=i+tx[d],dy=j+ty[d];
					if(dx<1||dx>a||dy<1||dy>b)
						continue;
					if(c[id(dx,dy)]==c[id(i,j)]){
						ma[id(i,j)][id(dx,dy)]=1;
						ma[id(dx,dy)][id(i,j)]=1;
					}
					t[id(i,j)]=c[id(i,j)];
				}
		for(int i=1;i<=a;i++)
			for(int j=1;j<=b;j++)
				if(!vi[id(i,j)]){
					qu.push((no){i,j});
					while(!qu.empty()){
						no x=qu.front();
						qu.pop();
						int e=x.x,f=x.y;
						vi[id(e,f)]=1;
						for(int t=0;t<4;t++){
							int dx=e+tx[t],dy=f+ty[t];
							if(dx<1||dx>a||dy<1||dy>b)
								continue;
							if(!vi[id(dx,dy)]&&c[id(dx,dy)]==c[id(e,f)]){
								int xx=fd(id(e,f)),yy=fd(id(dx,dy));
								ma[xx].erase(yy);
								ma[yy].erase(xx);
								mg(ma[xx],ma[yy]);
								p[xx]=yy;
								qu.push((no){dx,dy});
								vi[id(dx,dy)]=1;
							}
						}
					}
				}
		for(int i=1;i<=q;i++){
			int xx=fd(id(l[i],r[i]));
			t[xx]=v[i];
			for(unordered_map<int,int>::iterator it=ma[xx].begin();it!=ma[xx].end();it++){
				int a=it->first,b=it->second;
				int yy=fd(a);
				ma[xx].erase(yy);
				ma[yy].erase(xx);
				p[yy]=xx;
				mg(ma[xx],ma[yy]);
			}
		}
		for(int i=1;i<=a;i++){
			for(int j=1;j<=b;j++)
				printf("%d ",t[fd(id(i,j))]);
			puts("");
		}
	}
}