問題はこっち
http://hamayanhamayan.hatenablog.jp/entry/2017/01/23/014337
参考
https://www.facebook.com/notes/1607098535972708
https://togetter.com/li/1073027
12: Subtle Sabotage
これは場合分けをして解く。
本番では、3番目のテストケースの答えが5になるのが、まず分からなかった。
公式Editorialで見られるような感じのやつを想定して場合分けする。
22: Big Top
Bはサイズ[10200000]の高さテーブル持っておいて柱の周辺±H[i]を愚直にループ回しつつ更新しましたね
— iwashi31 (@iwashi31) 2017年1月21日
マジでって感じ。
解答はsetで棒を管理する解法。
棒の集合はある棒がある棒に完全に包含される状態を含まない状態を保ちながら更新していく。
ある棒を追加する場合は左右に対して完全に包含されるかを判定して、完全に包含されるならば消していく。
一見、かなり時間が掛かりそうな感じがあるが、ある棒について消されるのは1回のみであるため、消す回数はO(N)に収まり、大丈夫。
領域のマージをする時にこんな問題を見たことがある。
若干、典型問題なのだろうか。
