yukicoder 1373 Directed Operations
頂点$ iにたどり着くためには, 直前までの要素にすべてたどり着けるなら, 頂点$ i-1, i-2, ...から少なくとも1つ辺があればよい. これを順に見ていくことによって解けるので, 1つ辺を張ることができるか？という判定問題を解くことを考える.
ここでARC105 C Camels and Bridgeのように, pairを持って二分探索をすることを考える. pairの要素には$ a_iと$ iを持ち, 今回は削除という操作も高速にしたいのでsetをもつ. これが分かれば上手く実装すると解ける. 計算量は$ O(N log N)となる.
実装例: https://yukicoder.me/submissions/613492