ARC069 E - Frequency (700)
解いている最中は効率的にどこにカウントされるかを計算する方法が分からなかった
取るのは一番残りが多い場所が良い
できるだけ早く前のを取れるようにするため
同じ残りではできるだけ後ろから取りたい
辞書順最小にするためにできるだけ前のを残したい
$ a_iの大きい順かつiの大きい順に見ていく
一番最後に$ (0,-1)の組があることにする
1つの場所で取り除かれる石は$ a_i - a_{i+1}個
取り除かれる場所はこれまで見てきた場所全てのため、$ i+1箇所になる
今まで見てきた場所は全て残りの数が同じなので一番左の場所でカウントすることができる
ペアのソートがボトルネックで$ O(N \log N)