我发现我根本不会 dp，然后我找点题做
CF1859D *1800
离散化，设 \(r_i\) 表示 \(i\) 的原值，dp 一个 \(f_i\) 表示在区间 \([r_i,r_{i+1})\) 起始的答案。
容易发现，我们向后跳是一定不优的，设当前在 \(p\)，如果要向后跳那么一定是为了之后的向前跳到一个新的位置 \(r>p\)，然而我们发现这样的话 \(p\) 也一定包含在 \(r\) 的大区间里面，这样就无需向后跳了。
类似的证明可以发现一定是跳到 \(b_i\) 上，因此从右往左扫，维护当前所有能跳到的 \(b_i\)，选取最大的一个用 \(f_{b_i}\) 更新 \(f\)，可以用 multiset 实现，时间复杂度 \(O(n\log n)\)。
CF1859E *2500
拆绝对值
标签：发现,区间,点题,一定,妹子,dp From： https://www.cnblogs.com/yukari1735/p/17648331.html