$hint1:$

• 三角形重叠并不优。

$hint2:$

• 考虑列出暴力的 $dp$ 转移方程，并尝试使用线段树优化。

$hint3:$

• 观察行变化时 $dp$ 中的转移代价如何变化，复杂度 $O(n\log n)$。