読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

AOJ1330 Never Wait for Weights

問題文

Never Wait for Weights | Aizu Online Judge
日本語訳は他の方のブログ見てください

解法

!を頂点の連結クエリ,?を連結成分内のrankの差を取得するクエリとしてみてみましょう.
Union-Findしたい気持ちになってくると思います.
Union-Findについて,自分の親を連結成分内の最もWeightの大きい頂点とすると,重みの差の一意性っぽいものができそうです.
頂点の順位が独自に決めていいわけではなく与えられるため,蟻本のような実装だとうまくいかないです.
ところが,rankによる処理を行わなくてもfind時の親の付け替えを行うだけで全体のならし計算量がO(logN)になります.
これを利用するとO(QlogN)で解けます.

実装上の工夫としては,親からの距離をrank(v)に保持しておき,find時にセグ木の遅延評価のような処理を施すと更新が楽になると思います.

    int find(int x){
	if(par[x]==x)return x;
	else{
	    int p=find(par[x]);
	    rank[x]+=rank[par[x]];
	    return par[x]=p;
	}
    }