yukicoder : No.2295 Union Path Query (Medium)

こちらもどうにか解けた。
https://yukicoder.me/problems/no/2295

問題

N頂点の無向グラフを考える。初期状態で辺はない。
ここに重み付きの辺を加えて行くとする。
2点u,vの距離は、u-v間のパスにおける辺の重みの最小値とする。

以下のクエリに順次答えよ。

• 指定された2点間を指定の重みの辺でつなぐ。辺の重みは単調増加である。
• 指定の2点間の距離を求める
• 1点指定されるので、その点が含まれる連結成分において、全点間の距離の総和を求める

解法

辺の重みが単調増加であることから、マージテクの要領で連結成分をつないでいこう。
3つ目のクエリは、連結成分内の距離の総和を常に覚えておくことで容易に答えられる。
問題は2つ目であるが、今回の問題では2つ目のクエリは先読み可能である。
そこで、各頂点に対しその点が含まれるクエリ番号を覚えておき、マージテクの要領で連結成分をつなぐときに、2つ目のクエリの解を計算していこう。

ll SD[202020];

set<int> S[202020];
int AA[302020],BB[302020],CC[302020];
int C[202020];
int N,X,Q;
const ll mo=998244353;
map<pair<int,int>,int> ret;
set<int> cand[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X>>Q;
	FOR(i,N) {
		C[i]=i;
		S[i].insert(i);
	}
	FOR(i,Q) {
		cin>>AA[i]>>BB[i];
		
		if(AA[i]==1) {
			cin>>CC[i];
		}
		if(AA[i]==2) {
			cin>>CC[i];
			if(BB[i]==CC[i]) {
				ret[{BB[i],CC[i]}]=0;
			}
			else {
				cand[BB[i]].insert(CC[i]);
				cand[CC[i]].insert(BB[i]);
			}
		}
	}
	
	FOR(i,Q) {
		if(AA[i]==1) {
			int a=C[BB[i]];
			int b=C[X];
			if(a==b) continue;
			if(S[a].size()<S[b].size()) swap(a,b);
			SD[a]=(SD[a]+SD[b]+1LL*S[a].size()*S[b].size()%mo*CC[i])%mo;
			
			FORR(c,S[b]) {
				FORR(d,cand[c]) if(S[a].count(d)) {
					ret[{c,d}]=ret[{d,c}]=CC[i];
				}
			}
			FORR(c,S[b]) {
				C[c]=a;
				S[a].insert(c);
			}
			S[b].clear();
		}
		else if(AA[i]==2) {
			if(C[BB[i]]!=C[CC[i]]) {
				cout<<-1<<endl;
			}
			else {
				assert(ret.count({BB[i],CC[i]}));
				x=ret[{BB[i],CC[i]}];
				cout<<x<<endl;
				X=(X+x)%N;
			}
		}
		else if(AA[i]==3) {
			cout<<SD[C[BB[i]]]<<endl;
		}
		else if(AA[i]==4) {
			X=(X+BB[i])%N;
		}
	}
}

まとめ

一見クエリ先読みが出来なさそうでできるのがコツ。