yukicoder : No.2294 Union Path Query (Easy)

ここらへんはまだどうにか解けた。
https://yukicoder.me/problems/no/2294

問題

初期状態で辺のない無向グラフを考える。
このグラフにおいて、2頂点の距離は各辺の重さのxorで計算できるものとする。
以下のクエリにオンラインで処理せよ。

• 非連結な2頂点が指定されるので、指定された重さの辺でつなぐ。
• 指定された2頂点が同一連結成分内にあるか判定し、同一連結成分内なら距離を答える。
• 指定された頂点が含まれる連結成分内に含まれる頂点の対における距離の総和を求めよ。

解法

いわゆるマージテクを使い、連結成分毎に以下を求めておく。

• 連結成分に含まれる頂点一覧
• 連結成分中で根を定めたとき、根から各点までの辺の重みのxor
• 上記xorの値を2進数表記したとき、各bitが0/1となっているものの個数

1つ目のクエリに対しては、頂点数の少ない方を、大きい方に接続し、「根から各点までの辺の重みのxor」「各bitが0/1となっているものの個数」を更新していけばよい。

int SC[202020];
int num[202020][31];

set<int> S[202020];
int C[202020];
int N,X,Q;
const ll mo=998244353;

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);
	}
	while(Q--) {
		cin>>i;
		if(i==1) {
			cin>>x>>y;
			int a=C[x];
			int b=C[X];
			int p=x,q=X;
			if(S[a].size()<S[b].size()) swap(a,b),swap(p,q);
			int t=SC[p]^SC[q]^y;
			FORR(c,S[b]) {
				C[c]=a;
				SC[c]^=t;
				FOR(j,30) if(SC[c]&(1<<j)) num[a][j]++;
				S[a].insert(c);
			}
			S[b].clear();
		}
		else if(i==2) {
			cin>>x>>y;
			if(C[x]!=C[y]) {
				cout<<-1<<endl;
			}
			else {
				i=SC[x]^SC[y];
				cout<<i<<endl;
				X=(X+i)%N;
			}
		}
		else if(i==3) {
			cin>>x;
			ll ret=0;
			x=C[x];
			y=S[x].size();
			FOR(i,30) {
				ll a=1LL*num[x][i]*(y-num[x][i])%mo;
				(ret+=a<<i)%=mo;
			}
			cout<<ret<<endl;
			
		}
		else if(i==4) {
			cin>>x;
			X=(X+x)%N;
		}
	}
}

まとめ

いわゆるUnion-Findのデータ構造自体は使わなかったな…。