容易将问题转化为选择 $k$ 个分界点，使得任意保留的区间至少跨过一个分界点。相当于要将相邻两个分界点之间的所有区间删去。

外层对 $k$ 套用 Aliens' Trick 从左往右 DP，那么需要数据结构支持查询全局最小值，末尾插入新元素，前缀加这些操作。使用线段树维护即可做到 $\mathcal{O}(n \log n \log nV)$。

若前面的元素已经比后面的元素大，由于加操作均为前缀操作，所以前面的元素可以直接删除。使用并查集维护每个位置的上一个未被删除的位置和下一个未被删除的位置，以及相邻两个未被删除位置的差值，和最后一个未被删除位置的真实值，即可做到均摊 $\mathcal{O}(1)$ 次并查集操作维护这个问题。使用线性序列并查集即可做到 $\mathcal{O}(n \log nV)$。