JOI 2019 予選 E - イルミネーション

• 問題
• AC

木の番号を$0, ..., N-1$として考える。選んだ木のうちいちばん右のものが$x-1$である場合の美しさの最大値を$f(x)$とする。$x$と同時に選べない木 $t \le x$ でもっとも左にあるものを$\lambda (x)$とするとき、$f$の漸化式は

$f(x) = A_{x-1} + \max_{t \le \lambda (x-1)} f(t)$

と書ける。

上の漸化式に従って素朴にDPすると${\mathcal O}(n^2)$になるので、累積和$S(x) = \max_{0 \le t \le x} f(t)$で考える:

$\begin{aligned} S(x) & = \max(f(x), S(x-1)) \\ & = \max(A_{x-1} + S(\lambda(x-1)), S(x-1)) \end{aligned}$

求める答えは$S(n)$なので、$S$に関してDPすればよい。

さて、$\lambda(x)$をどう求めるかが問題だが、長さ$N$のセグメント木$\lambda$を作って$\lambda[x] := x$と初期化し、各区間$[L, R]$を区間$\min$で$L$に更新するという方法でテーブルを作った。この場合、計算量は${\mathcal O}(N + M\log N)$になっている。

解説を見ると${\mathcal O}(N+M)$でできるらしい。長さ$N$の配列$\lambda$をやはり$\lambda [x] := x$で初期化し、各クエリ$(L, R)$を$\lambda[R] := \min(\lambda[R], L)$で処理したあと、後ろから$\lambda[x] := \min (\lambda [x], \lambda [x+1])$と更新していけばテーブルができている。なるほど……

線型でできそうという感じは確かにしたけど、少し複雑になると累積和的なやり方がぱっと出てこない。