ABC134E
E - Sequence Decomposing
https://gyazo.com/3f50fa55b41f2b055b35ff78691f2614
考えたこと
同じ色のグループに着目すると単調増加列になっている
先頭から見ていって単調増加なら同じ色で塗る、という貪欲法でOKなのかを考える
ある最良解である値xが単調増加なのに選択されてないとする
列がxの手前で終わってるか、xの先でxより大きい値yになってる時、コストを増やさずにxを追加できる
そうでない時
yではなくxを選択することでyから開始する列が1つ増えるが、xから始まる列が1つ減るので損はしない
ただしxがもっと手前から始まる別の列に入ってる場合は別
よって下記の貪欲法でOK
先頭から見ていく、既に存在するどの単調増加列にも入らないなら新しい単調増加列を追加する
追記: 入る場合の入れ方に関して考察漏れ
公式解説
最長の広義単調減少列に一致する、としてO(Nlog N)
LIS(最長増加部分列)問題に帰着
Dilworthの定理
自分実装
既に存在する単調増加列の複数に入りうる時に自由に入れられるわけではないと気づいた
2,1,4,5,3で、5は4の入った列に入れなければならない
つまりこれ、入れる数より小さくて最大の値を見つけなければならない
線形探索すると最悪ケースでTLEしそう
対象が静的でないからソートして二分探索というわけにはいかない
フェニック木で二分探索か…値の範囲が10^9だなぁ
この方針でやるなら座標圧縮→フェニック木→二分探索という流れになるな
この前処理や、本処理で二分探索が必要になるところから計算量は公式解説と同じオーダーになる
公式解説
僕と逆に後ろから見ている
制約を満たす中で最小のものを選ぶのは僕の「入れる数より小さくて最大の値」を選ぶ方法の裏返し
フェニック木を使う方法は最長増加部分列の解法の一つ
なるほど、「xを超えない最大の値をxに更新」はソートされた状態を維持するのか
更新され二分探索できる配列