Codeforces ECR #082 : F. Number of Components

本番なんで解いてないんだろ。
https://codeforces.com/contest/1303/problem/F

問題

N*Mのグリッドがあり、それぞれ初期値は0である。
セルを1つ指定し、値を更新するクエリが与えられる。
なお、与えられる値は正でかつ昇順である。

クエリ更新毎に、隣接する同値のセルを連結しているとみなしたときの連結成分数を答えよ。

解法

• 値cとなるセルが増えることによる連結成分の増減
• 値cと関係ないセルによる連結成分
• 値cじゃなかったものがcになってしまうことによる連結成分の増減

をそれぞれ考えよう。

まず、更新する値が同じcとなる一連のセルをまとめて処理して1つ目を求める。
これらのクエリを順に処理して値cとなったとき、cで構成される連結成分数を順次計算しよう。
次に、クエリの影響を受けないセルを一通りUnion-Findで処理して連結成分を数え上げ2つ目を求める。。
最後に3番目だが、値cとなるクエリを逆向きに巻き戻すことで、cじゃなかったものがcになってしまう影響を求めることができる。

class UF {
	public:
	int um; vector<int> par,rank,cnt;
	UF(int um_) {um=um_;par=rank=vector<int>(um,0); cnt=vector<int>(um,1); reinit();}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}

	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};


int H,W,Q;
int A[302][302];
int B[302][302];
int L[302][302];
vector<pair<int,int>> V[2020200];
int ret[2020202];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&H,&W,&Q);
	FOR(i,Q) {
		scanf("%d%d%d",&y,&x,&j);
		V[j].push_back({y-1,x-1});
	}
	
	int st=0;
	UF uf(H*W);
	for(i=1;i<=2000000;i++) if(V[i].size()) {
		FOR(y,H) FOR(x,W) B[y][x]=A[y][x];
		uf.reinit();
		int num=0;
		FOR(j,V[i].size()) {
			y=V[i][j].first;
			x=V[i][j].second;
			if(B[y][x]!=i) {
				num++;
				B[y][x]=i;
				L[y][x]=j;
				if(y&&B[y-1][x]==i&&uf[y*W+x]!=uf[(y-1)*W+x]) num--, uf(y*W+x,(y-1)*W+x);
				if(y+1<H&&B[y+1][x]==i&&uf[y*W+x]!=uf[(y+1)*W+x]) num--, uf(y*W+x,(y+1)*W+x);
				if(x&&B[y][x-1]==i&&uf[y*W+x]!=uf[y*W+x-1]) num--, uf(y*W+x,y*W+x-1);
				if(x+1<W&&B[y][x+1]==i&&uf[y*W+x]!=uf[y*W+x+1]) num--, uf(y*W+x,y*W+x+1);
			}
			ret[st+j]=num;
		}
		uf.reinit();
		FOR(y,H) FOR(x,W) if(B[y][x]!=i) {
			if(y&&B[y-1][x]==B[y][x]) uf(y*W+x,(y-1)*W+x);
			if(x&&B[y][x-1]==B[y][x]) uf(y*W+x,y*W+x-1);
		}
		num=0;
		FOR(y,H) FOR(x,W) if(B[y][x]!=i && uf[y*W+x]==y*W+x) num++;
		for(j=V[i].size()-1;j>=0;j--) {
			ret[st+j]+=num;
			y=V[i][j].first;
			x=V[i][j].second;
			if(L[y][x]==j) {
				B[y][x]=A[y][x];
				num++;
				if(y&&B[y-1][x]==A[y][x]&&uf[y*W+x]!=uf[(y-1)*W+x]) num--, uf(y*W+x,(y-1)*W+x);
				if(y+1<H&&B[y+1][x]==A[y][x]&&uf[y*W+x]!=uf[(y+1)*W+x]) num--, uf(y*W+x,(y+1)*W+x);
				if(x&&B[y][x-1]==A[y][x]&&uf[y*W+x]!=uf[y*W+x-1]) num--, uf(y*W+x,y*W+x-1);
				if(x+1<W&&B[y][x+1]==A[y][x]&&uf[y*W+x]!=uf[y*W+x+1]) num--, uf(y*W+x,y*W+x+1);
			}
		}
		
		FOR(j,V[i].size()) {
			y=V[i][j].first;
			x=V[i][j].second;
			A[y][x]=i;
		}
		
		st+=V[i].size();
	}
	FOR(i,Q) _P("%d\n",ret[i]);
	
}

まとめ

コードは多くてややこしいけど、アルゴリズム自体はシンプル。