競プロ 数値配列で、その要素以降で自身以上の値の最小値の index を各要素について得たい [4, 1, 5, 9, 5, 7] から [2, 2, 4, -1, 5, -1]を得たい(-1 は該当無しの意)。
set を持つ
後ろから順に見て行き、 各要素について
lower_bound で該当する index を得る
set に追加
というのが素直な$ O(N \log N)なアプローチ。
---
他に、以下のようなアプローチがある。
各 index $ i に対する求める値を $ f(i) とする
stack を持つ。各要素の index を持つこととなる。
index を対応する要素の値の昇順に並べ(同一の場合は index の昇順)、各要素 $ iについて
「stack の末尾 $ jが $ i より小さい場合、pop する。この時 $ f(j) = iを得る 」を繰り返す
stack に $ i を push する
これがうまくいく理由の説明は以下。
stack の中身は「その時点で $ f(i) が定まっていないもの」となる
値の昇順で処理しているため、「stack の末尾 $ j が $ i より小さい」⇒「$ iが初めて$ jに対応する値以上の値を与える index である、かつ、$ jより後の index である」
補足として、stack は常に降順となる
ソートがネックで $ O(N \log N)。
---
を通じて初めて知ったアプローチ。