RT，线段树优化dp，即使是板子都有紫：https://www.luogu.com.cn/problem/CF115E

这题不应该评蓝把。