問題リンク

解説

年齢が若い順に見ていきます。

すると、それぞれの辺を加えるか削除するかがわかり、各頂点の左端と右端がわかります。

この更新は遅延セグ木や双対セグ木を用いて、 でできるので解けました。

提出コード

atcoder.jp