[CEOI2017]Building Bridges

时间限制：1000MS      内存限制：131072KB

难度： \(7.2\)

• 题目描述

有 \(n\) 根柱子依次排列，每根柱子都有一个高度。第 \(i\) 根柱子的高度为 \(h_i\) 。

现在想要建造若干座桥，如果一座桥架在第 \(i\) 根柱子和第 \(j\) 根柱子之间，那么需要 \((h_i-h_j)^2\) 的代价。
在造桥前，所有用不到的柱子都会被拆除，因为他们会干扰造桥进程。第 \(i\) 根柱子被拆除的代价为 \(w_i\)​，注意 \(w_i\) 不一定非负，因为可能政府希望拆除某些柱子。

现在政府想要知道，通过桥梁把第 \(1\) 根柱子和第 \(n\) 根柱子连接的最小代价。注意桥梁不能在端点以外的任何地方相交。

• 输入格式

第一行一个正整数 \(n\) 。

第二行 \(n\) 个空格隔开的整数，依次表示 \(h_1, h_2, \cdots, h_n\) 。

第三行 \(n\) 个空格隔开的整数，依次表示 \(w_1, w_2, \cdots, w_n\) 。

• 输出格式

输出一行一个整数表示最小代价，注意最小代价不一定是正数。

• 样例输入

• 样例输出

• 数据范围与提示

对于 \(30\%\) 的数据，有 \(1 \leq n \leq 1000\) ；

对于另外 \(40\%\) 的数据，有 \(\left| w_i \right| \leq 20\) ，保证存在一种最优方案，除了头尾两根柱子外，最多只保留两根柱子；

对于 \(100\%\) 的数据，有 \(2 \leq n \leq 10^5\)，\(0 \leq h_i,\left| w_i\right| \leq 10^6\) 。

数据来源 LOJ 2483 。

 

 

已搬至 YZOJ P4254 。

---

 

 

 

按照惯例，设 \(f_i\) 为做到第 \(i\) 根柱子时的最小代价。计 \(sumw\) 为 \(w\) 的前缀和。

轻松得到转移方程 \(f_i=\min\limits_{j=1}^{i-1}\{f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2\}\) ，这样就有了 \(30pts\) 。

 

不难发现其实这是一个斜率优化的经典模型。对这个转移方程进行一些处理

\(\begin{align} f_i&=f_j+sumw_{i-1}-sumw_j+(h_i-h_j)^2 \\ \underbrace{f_i}_{b_i}&=\underbrace{f_j-sumw_j+h^2_j}_{y_j}-\underbrace{h_i}_{k_i} \cdot \underbrace{2h_j}_{x_j}+\underbrace{sumw_{i-1}+h^2_i}_{const_i} \end{align}\)

但是问题来了，这里的 \(k_i\) 和 \(x_j\) 都不是单调的。哦豁，完蛋，要写 Splay 维护下凸壳了。这个时候就要用到一种神奇的分治算法 —— CDQ分治。

回顾一下斜率优化的写法：把可以实现把一个点加入单调队列的操作是因为加入的 \(x\) 是单调的，可以取队头元素为最小值是因为询问的 \(k\) 是单调的。CDQ 分治就是牢牢抓住这两点进行操作的。

因为是分治，所以要有一个分治区间 \([l, r]\) 表示用 \([l, mid]\) 中所有点的信息去更新 \((mid, r]\) 的最小值。那么如何快速做到这个更新操作呢？？？很简单，只需要把 \([l, mid]\) 中的点按照 \(x\) 排序，\((mid, r]\) 中的元素按照斜率 \(k\) 排序，这样就可以按照最简单斜率优化的写法去更新了。

直接在里面 std::sort()  复杂度会多个 \(log\)（虽然对于数据水的本题也能过），但是运用归并排序的思想就可以达到 \(O(Nlog^2N)\) 的复杂度。

首先在外面把元素按照斜率 \(k\) 排序，然后开始 CDQ分治。

对于区间 \([l, r]\) ，把其中元素的编号按照与 \(mid\) 的大小进行分类，\(\leq mid\) 的分到左边，\(>mid\) 的分到右边，因为要用 \([l, mid]\) 中的点更新 \((mid, r]\)，所以要先把这些点找出来。

接着递归进 \([l, mid]\) ，保证左区间已经被处理过了，才能更新右区间的元素。

现在左区间的点和信息都被处理好了，并且 \(x\) 是单调的（已经被处理好了，详见后述），加上右区间的元素的斜率 \(k\) 是单调的（还没有被处理过），所以就可以把左区间的点加入单调队列，然后去更新右区间的元素。

但是现在 \((mid, r]\) 中的元素只有来自 \([l, mid]\) 的贡献，可能取不到最优解，所以还要递归进 \((mid, r]\) 继续处理右区间。

最后不要忘了，要利用归并排序将 \([l ,r]\) 中 点的 \(x\) 变为单调的，这样才能保证前面操作的正确性。（可以理解为递归进一个区间后，这个区间内点的 \(x\) 就会被处理成单调的，可以进行后续的操作）

这就是 CDQ分治 的大致过程。