yukicoder No.1170 Never Want to Walk

問題

https://yukicoder.me/problems/no/1170

座標がである個の駅がある。のとき、駅と駅に無向辺が張られている。各駅が含まれる連結成分の数を求めよ。

解法

座標が小さい順に見ていく。

Union-Findを用いて、各駅における、からの間に存在する駅を（二分探索等で列挙し）uniteすることで、で求めることができるが、これだとTLEしてしまう。

そこで、尺取り法を用いる。
具体的には、一つ前の駅において最後に辺が張られた駅（無ければ自分自身）を保存しておき、そこから探索を始める。
そうすることで、一つ前の駅と範囲が被っている部分は、最後に辺が張られた駅がuniteされることでカバーされるため、重複部分を探索する必要がなくなり、おおよそで求めることができる。

コード

https://yukicoder.me/submissions/530719

一言

尺取り法楽しい。