rt，dp 不是很难想吧，而且即使有人没想到线性用线段树优化 dp 的话也是可以绿的吧。