思路

首先我们根据贪心的策略，很容易想出来一定要把最上边的那一行和最左边的那一列全部连起来，剩下的点连向左边或者上边就可以了。$O(n ^ 2)$ 的暴力做法就是枚举每个点是连向左边还是上边，直接加上每个点的贡献就可以了。

对于 $O(n \log n)$ 的做法，我们就不能挨个考虑每个点连接的方向了。我们进而分析每个点连接的方向和数组 $a, b, c, d$ 的关系。 显然，我们选择连上面而不是左边时，满足：

$$ a_{i - 1} + b_j < c_i + d_{j - 1} $$

移项，得

$$ a_{i - 1} - c_i < d_{j - 1} - b_j $$

即

$$ d_{j - 1} - b_j > a_{i - 1} - c_i $$

而对于每一行来说，$a_{i - 1} - c_i$ 是固定不变的。所以我们可以预处理好 $d_{j - 1} - b_j$ 的值，记作 $diff$，每次在 $diff$ 上二分 $a_{i - 1} - c_i$ 的值，这个值右边的所有数就是连向上面的，左边的所有数就是连向左边的，进而我们可以求出连向上面和左边的点的个数，分别记作 $n_U$ 和 $n_L$。

对于计算贡献，我们可以把 $a, c$ 和 $b, d$ 分开考虑。$a, c$ 的计算比较简单，我们只需要加上 $n_U$ 个 $a_{i - 1}$ 和 $n_L$ 个 $c_i$。$b, d$ 的处理比较麻烦一些，我们可以把 $b_j, d_{j - 1}, d_{j - 1} - b_j$，放在一个结构体里，按照 $diff$ 值排序之后，对 $b$ 和 $d$ 做前缀和，二分位置前的加上 $d$，位置后的加上 $b$ 就可以了，当然也有其他的方法，这里就不多说了。

代码

代码实现时需要注意一点小细节，自己想想就明白了。

AC Record