Educational DP Contest Q コード 問題 前から順に見て行く. 高さ \(h_i\) の木が部分列の最後の木になるときの最大の美しさを \(B(h_i)\) とすると, これは \[B(h_i) = \max_{h_j \lt h_i} B(h_j) + a_i\] となる. これをセグメントツリーで管理する. 計算量は \(O(N \log N)\) である.