ARC104 F - Visibility Sequence の別実装例

ネタバレ注意

解説ではボトムアップ (?) に区間を計算していく方法を紹介していましたが、区間を分割していくという視点でも書くことができ、こちらは意識せずとも 4 乗の解法が作れます。

少し数え方の方針が違って、

区間 [l,r] の中で、-1を見ているような一番右のもの、を固定するとそこの値はできるだけ大きくするのが最適です (そのようなものはleft-to-right maxima であって、左も右も条件がゆるくなる) そこで分割すると、左と右の上限が決まります。

よって f(l, r, mx) : 区間 [l, r] を見ていて全ての値が mx 以下、とすると、上述の点ごとに次の左右のmxの値は1つしか遷移しなくていいので単純なメモ化再帰でよいです。