EDPC Q - Flowers

考え方

左から順に、その花を最後に残す場合の最大値を求めていけばよい。
その値は、自分より前にある自分より低い花の中での最大値+自分の価値とすればよい。
$O(N^2)$ でよいのであれば、これで簡単。

あとは高速化だが、最大値を取得できるsegment木を用いるのが有効。
花 $1$ 本を処理するごとに、最後の花の高さが $i$ である場合の情報を位置 $i$ に入れてやる。
すると、「高さが自身未満の中で最大値」を $O(\log N)$ で取得できる。
これで全体計算量は $O(N\log N)$ となる。

最後の答えは、任意の花を最後に残した場合の最大値であり、つまりsegment木の全体処理した値である。

入力例1での動作

入力を受け取る。

n: 4
h: {3, 1, 4, 2}
a: {10, 20, 30, 40}

高さごとに、その高さの花を最後に残す場合の最大価値を持つ。

高さ $1$ から $4$ までについて、最初は全て $0$ である。

{0, 0, 0, 0}

$1$ 本目は高さ $3$、価値 $10$ である。
高さ $3$ 未満の範囲の最大値は $0$ である。
したがって、高さ $3$ の位置に $0+10=10$ を入れる。

{0, 0, 10, 0}

$2$ 本目は高さ $1$、価値 $20$ である。
高さ $1$ 未満には花がないので、最大値は $0$ である。
高さ $1$ の位置に $20$ を入れる。

{20, 0, 10, 0}

$3$ 本目は高さ $4$、価値 $30$ である。
高さ $4$ 未満の範囲では、最大値は高さ $1$ の $20$ である。

したがって、高さ $4$ の位置に $20+30=50$ を入れる。

{20, 0, 10, 50}

$4$ 本目は高さ $2$、価値 $40$ である。
高さ $2$ 未満の範囲の最大値は、高さ $1$ の $20$ である。

したがって、高さ $2$ の位置に $20+40=60$ を入れる。

{20, 60, 10, 50}

ここで必要なのは毎回「自分の高さ未満の範囲の最大値」である。
この範囲最大値の取得と、各高さの値の変更を segment 木で行う。

最後に全範囲の最大値を取ると $60$ である。
したがって、答えは $60$。

注意点

答えは、int 型からはみ出る。
long long 型を用いること。

別解

特になし。