技術室奥プログラミングコンテスト#4 Day2：E - 引きこもり

問題
解法
解答

問題

https://atcoder.jp/contests/tkppc4-2/tasks/tkppc4_2_e

解法

まず，辺のコストを座標圧縮しておき扱いやすくしておく．また，辺を辺のコストが昇順になるようにソートしておく．その後 L を 0 から増やしていったときにどのように連結成分の大きさが変化していくかを考える．現在連結である頂点は Union-Find 木を用いて管理することができる．Union-Find 木での結合の操作時に，その連結成分に含まれる頂点の個数を数えておき，各連結成分の大きさを一点更新・区間最小取得のセグメント木で管理しておく．こうすることで，L を +1 したときに各連結成分の大きさの最小を得ることができる．これらの情報を配列にまとめることで「L = k としたときに一番天使に会えない天使たちが会うことのできる天使の数」を調べることができる．問題で問われているのは，天使の数から L を得ることであるから，この情報を少し変換することで各天使の数から L を求めることができるようになる．よって，前計算 O(MlogN) 各クエリ O(1) で解くことができた．