No.284

最長部分門松列列を求める問題である.

$A_i$ は座標圧縮しておく.

まずは $A_i$ がすべて異なる場合を考える.

長さ $a$ が右端で, そのすぐ左側の長さが $a$ より大きい部分列の最大の長さを $B_{\gt}(a)$ とし, 同様にすぐ左側の長さが $a$ より小さい部分列の最大の長さを $B_{\lt}(a)$ とする.

そして $A_i$ を前から順に見ていくと,

$$B_{\gt}(A_i) = \max_{a \gt A_i} B_{\lt}(a) + 1 \\ B_{\lt}(A_i) = \max_{a \lt A_i} B_{\gt}(a) + 1$$

となる. $B(a)$ は最大値を計算する Segment Tree で管理すれば $O(N\log N)$ で計算できる.

さて, 実際は $A_i$ は同じ数値のものがあるので, そこをどうするか.

そこで, $B(a)$ には [最大長, 自身の長さ, すぐ左側の長さ] をセットで保存するようにする. また, すぐ左側の長さが $A_i$ と同じ場合はそのセット使えないので, [2番目に大きい長さ, 自身の長さ, すぐ左側の長さ] のセットも保存するようにする.

そして, Segment Tree の最大値を計算する部分は, 最大長と2番目の長さを計算するようにする. このとき, 最大長とセットのすぐ左側の長さと2番目の長さとセットのすぐ左側の長さは異なるように計算する.

こうすることで, 最大長とセットすぐ左側の長さが $A_i$ と同じ長さの場合は2番目の長さを使えばいいことになる.

また, Segment Tree の更新であるが, 最大長は上記で取得したものを使う.上記で取得した自身の長さを除いて再度 Segment Tree に問い合わせる.