037 - Don't Leave the Spice（★5）
ナップサックを1次元でやるやつをSegment Tree上で行えばよい（インラインDP）
$ dp(i):=
香辛料を
$ i
使用した として、
$ [i-R,i-L]
の範囲の最大価値に現在の料理の価値を足したものと比較する。よって区間最大値を取得するSegment Treeがあればよい。
https://atcoder.jp/contests/typical90/submissions/59487047
スライド最小値でlogを落とせる。