2018年12月10日
情報オリンピック日本委員会
解説
小課題 1
海面の高さが整数の時点のみ調べればよい．
海面の高さが t の時，島の数は A_i > t となる i の連続した区間の個数である．これは O(N) 時間で求めることができる．例えば，A_0=0 とおいて，A_{i-1} ≦ t かつ A_i > t となる i の個数を数えればよい．
よって O(N max A_i) 時間で問題を解くことができる．
小課題 2
小課題 1 の解放において，海面の高さが 0 の時点およびある区画の高さと等しい時点のみ調べればよい．
よって O(N^2) 時間で問題を解くことができる．
小課題 3
ある状態から，陸地が一つ沈没したとき，それによって島の数が増えるか，減るか，変わらないかはその左右の区画を見ればわかる．どちらも陸地であれば島の数は増え，どちらも沈んでいれば島の数は減り，そのどちらでもなければ島の数は変わらない．
0, A_1, ..., A_N に現れる数を昇順にソートしたものを B_0, ..., B_M と置く．
海面の高さが B_{i-1} の時点と B_i の時点では，高さが B_i の区画が沈没すること以外は状態は変わらない．そのような区画それぞれについて上記の場合分けを見れば，海面の高さが B_{i-1} から B_i になる際の島の数の増減がわかる．そのような区画の番号たちは，A をソートする際に番号も一緒にペアにしてソートしておけばそこから取り出せる．
よって，海面の高さが B_0, ..., B_M の時点での島の数を順番に求めていくことがができる．各区画について高々一度しか上記の場合分けを見ないので，これは O(N) でできる．ソートに O(N log N) かかるので，全体で O(N log N) 時間でこの問題を解くことができる．
