Codeforces ECR #091 : E. Merging Towers

割としんどいけど全完できた回。
https://codeforces.com/contest/1380/problem/E

問題

1～Nの大きさの大きさのディスクが1枚ずつあり、M個のタワーに分けられている。
各タワーでは、ディスクが下から大きい順に積まれている。

以下の問題を考える。

• あるタワーのうち上から何枚か抜き取り、別のタワーの上に重ねる。その際、ディスクのサイズが下から大きい順に積まれている状態をキープしなければならない。
• 全ディスクを1つのタワーにまとめるのにかかる最小処理回数はいくつか。

この問題に対し、タワーをマージするクエリが与えられる。
マージ毎に、上記問題の解を求めよ。

解法

処理回数は、大きさの連続する2枚のディスクが別のタワーに属している箇所の数に一致する。
そこで、タワー毎にディスクの集合を持ち、いわゆるマージテクの要領で集合をマージしつつ、別のタワーに属する連続ディスクの数の差分を数えていこう。

int N,M;
int T[202020],A[202020];
set<int> S[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	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;
	}
};
UF<202020> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		S[x-1].insert(i);
		A[i]=x;
	}
	int num=0;
	FOR(i,N-1) if(A[i]!=A[i+1]) num++;
	cout<<num<<endl;
	FOR(i,M-1) {
		cin>>x>>y;
		x=uf[x-1];
		y=uf[y-1];
		
		if(S[x].size()>S[y].size()) swap(x,y);
		FORR(v,S[x]) {
			if(S[y].count(v-1)) num--;
			if(S[y].count(v+1)) num--;
		}
		FORR(v,S[x]) S[y].insert(v);
		S[x].clear();
		uf(x,y);
		if(uf[x]==x) swap(S[x],S[y]);
		cout<<num<<endl;
		
	}
	
}

まとめ

これはシンプルでECRのEぐらいにはちょうど良い問題。