【摘要】提供一种 \(O(n\sqrt n)\) 的做法。 考虑数据结构优化 DP。如果正序做，\(dp_i\) 为从 \(1\to i\) 的最大值，那么只能主动转移，转化成单点查和区间修。正难则反，设 \(dp_i\) 为从 \(i\to n\) 的最大值，被动转移，变成单点修和区间查。这显然更好做。 阅读全文