Stack

最近取得した方から使う

• ABC333 E - Takahashi Quest

last in first out の last in が効いてる

(last は最後や最近という意味がある)

単調減少列の管理 (Monotone Stack)

tbw: 数列に対して、単調減少になるように値を間引いた数列みたいなのを考える

パレート前線(パレート集合)は半順序関係における極小元の集合

単純に min を保持していればいいパターンとstack を持つパターンがありそう(右から見るか左から見るか

prefix のパレート集合をstack持って差分更新するか

全体のパレート集合をmin で求めるか

• $A_j < A_i,\ j < i$ を満たす最大の $j$ を求める (自分より小さい直近の場所を求める)
  • 下位互換を捨てるイメージ
  • パレード最適をスタックで管理しているイメージかもしれない
    • パレート最適の差分更新とも言えそう。
  • 全4パターン
    • 「$A_j < A_i$」 か 「$A_j > A_i$」
    • 「$j < i$ を満たす最大の $j$」か「$j > i$ を満たす最小の $j$」
• ABC372 D - Buildings
  • 条件を満たすものを管理すると単調減少になる
• ABC359 E - Water Tank
• ヒストグラム内の極大長方形 https://note.com/rikimarublack/n/n3074b0955e95
• cartesian tree の構築
  • セグ木でも作れるけど、Stack を使うと O(N) で作れる
  • https://atcoder.jp/contests/abc435/tasks/abc435_f