模拟赛

T2

首先对于一个序列而言，我们操作的最小代价就是他的逆序对数量

草我感觉像证结论然后贪心

但是我实在是没发现什么结论啊

T3

考虑先将图上所有点的连通性处理出来，我们发现接下来我们关注的只有这个联通块对应的行的区间

问题就变成了：给定若干个区间，要求用若干条垂线将其联通的最小代价

首先考虑将所有区间排序，然后扫描线，当某个区间的右端点被加入时则考虑更新答案

使用数据结构维护 $f_i$ 表示上一次修改在第 $i$ 行的最小代价

然后每次更新时找到当前区间内 “从右往左数第一个 1/2” 的位置，

连边的本质？

我们回到一开始，如果用dp我们会如何解决这个问题

我们会设 $f_{i}$ 表示在第 $i$ 行使用了一次，并且所有 $l$ 小于等于 $i$ 的区间都已经联通的最小代价

其实就相当于转化为一个序列分割问题

我们发现 $i$ 实际上的取值只有可能是每个区间从右往左数第一个 $1/2$ 的位置，于是决策点的级别就缩到 $O(k)$ 了

什么样的点可以转移呢？满足它左边所有区间的右端点的最大值比 $i$ 更大的

然后就做完了？