CSP-S T3 又一原题？

$rt$，trick 是一样的，二维 DP 最后用线段树维护。