公平坚果与矩形 题解

思路

按 $x$ 递增排序。由“不存在包含关系”可知 $y$ 严格递减。令 $dp_i$ 表示选择第 $i$ 个矩形作为最右边矩形时的最大收益，则

$$dp_i=x_i y_i-a_i+\max\left(0,\max_{j<i}(dp_j-x_jy_i)\right).$$

其中 $dp_j-x_jy_i$ 是斜率为 $-x_j$、截距为 $dp_j$ 的直线在 $y_i$ 处的值。

做法

子任务 1 枚举所有矩形子集，直接计算并集面积与代价。

子任务 2 使用上述递推枚举所有 $j<i$，复杂度 $O(n^2)$。

满分算法维护直线集合并做最大值查询。可使用离散 Li Chao 树，或利用斜率与查询横坐标都单调的性质维护凸包队列。

正确性证明

对任一以 $i$ 为最右矩形的选择，设此前最右矩形为 $j$。新增矩形贡献 $x_i y_i-a_i$，但与此前并集重叠的宽度为 $x_j$、高度为 $y_i$，故需减去 $x_jy_i$，此前最优收益为 $dp_j$。枚举全部 $j$ 并允许没有前驱，递推覆盖且只覆盖所有合法选择，因而正确。

复杂度

离散 Li Chao 树时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。