DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。
dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気にapplyメソッドで更新していく。
DPをしつつ、セグメント木で高速化する。 普段は配るDPで実装することが多いが、この問題では貰うDPで実装するほうが良さそう。
dpの更新は、セグメント木から前段のLからRの間の最大値を取得する。 セグメント木の更新は、dp[i]の値を一通り一気にapplyメソッドで更新していく。