自动搬运

查看原文

来自洛谷，原作者为

	水星湖 菜

搬运于2025-08-24 23:08:00，当前版本为作者最后更新于2025-01-05 21:37:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

设第 $i$ 个选择的矩形编号为 $b_i$，易得相交部分面积为:

$$\min_{1\le i \le k} x_{b_i}\times \min_{1\le i \le k} y_{b_i} $$

于是我们可以将每一对 $(x,y)$ 按照 $x$ 排序，用平衡树动态维护第 $k$ 大的 $y$ 即可。