KTT

观察 1: 这个区间其实跟左端点的关系不大，跟右端点关系更大。 于是我们可以想到从左到右考虑，于是乎我们发现了一个 $O(n^2)$ 的做法。 我们设我们当前决策了是否要激活 $[1,i]$ 且激活了 $i$ 的最大代价为 $f_i$。 然后转移就是枚举 $j < i$，然后减去多于代价，加上新的。 我们考虑优化他。 首先新的贡献是跟 $j$ 无关的。 然后剩下的呢，我们考虑我们往右扫。维护右端点在 $i$ 右边的区间。然后你把他们的左端点放在线段树里，你每删除一个线段，就在对应的区间内将线段树减一。然后相当于要区间 $y_i$ 加，区间 $x_iy_i$ 最小值。然后你发现这是 KTT 板子。 做完了。