ARC070C NarrowRectangles

题意 ： 有 个宽为 的木板从左到右排成一排，第 个木板覆盖了纵坐标 。

现在可以上下移动这些木板，使得所有木板连接起来（有一点接触就算连接）。问最小的移动距离和。

，时限 。

---

先考虑 。 设 表示处理了前 个木板，最后一个木板的左端点放在 ，所需的最小移动距离和。

显然，需要考虑的 均为整数。

不难写出转移方程：

是下凸函数，凸函数的区间 也是凸函数，于是不难归纳证明 是关于 的凸函数。

将 改记为 。

记 的最小值位置区间为 ，则可以写出转移方程：

这个方程相当于将 的左侧向左移动 ，右侧向右移动 ，然后加上一个绝对值函数。

对于绝对值函数的处理，分三类讨论：

用两个堆分别维护左右侧的凸壳，每个元素代表一个斜率变化 的拐点。

记加绝对值之前的函数，最小值区间为 ，记 。

• 情况A：

  最小值位置变为 。左侧斜率减一，右侧斜率加一，给左右两个堆各加入一个 。

• 情况B：

  查看 左侧的第一段斜率为 的区间，假设为 。

  则新的最小值区间为 。在左堆加入两个 ，因为斜率变化了两次。

• 情况C：

  情况类似，查看 右侧的第一段斜率为 的区间，假设为 。

  则新的最小值区间为 。在右堆加入两个 。

需要给堆维护一个整体加法标记。

还要考虑如何求解答案。记 为 的最小值，则：

• 情况A：最小值不变。

• 情况B：最小值加上

• 情况C：最小值加上

复杂度 。