题意
给你 \(n\) 个二维平面上的点，初始你有一个位于 \((0, 0)\) 的退化矩形。每次你可以选择一个点，并将矩形扩张（长、宽不能减小）使得矩形包含这个点，代价为新矩形相对于原矩形多出来的那部分。你需要判断有没有一种方案，使得最终矩形包含所有点且每一步的代价不超过给定的 \(m\)。
题解
首先把坐标离散化。考虑在对横坐标扫描线的同时计算。
先明确一些定义：
设 \(f_{i, j} = 0 / 1\) 表示是否存在一个满足条件的方案使得经过某些操作后，矩形的右上角为 \((i, j)\)。
设 \(p_{i, j}\) 表示所有点 \((a, b)\) 满足 \(a \le i\)，\(b \le j\) 中，横坐标的最大值。
设 \(g_{i, j} = f_{p_{i, j}, j}\)。
称一次转移 \(f_{a, b} \to f_{c, d}\) 中 \((a, b)\) 为“输出点”，\((c, d)\) 为“输入点”。
记集合 \(S\) 表示所有横坐标 \(\le i\) 的点的纵坐标组成的集合。
记 \(q_1 < q_2 < \dots\) 为所有满足横坐标 \(= i\) 的点的纵坐标从小到大排序组成的序列。
则有以下几种转移：
- 只有横坐标变大。
对于一个在这种情况被转移的 \((i, j)\)，他的输入点一定为 \((p_{i, j}, j)\)，因为你往左肯定更劣。
显然，\(p_{i, j}\) 随 \(j\) 增加单调不降，则对于相同的 \(p\)，\(j\) 构成一个连续段。
又对于这种情况，其代价为 \(j + 2(i - p_{i, j}) \le m\)，即 \(j \le m - 2(i - p_{i, j})\)，则对于每个连续段，可以转移的只有一段前缀，找出来是容易的。转移只需要将 \(f_{i, j} \to g_{i - 1, j}\)。
- 只有纵坐标变大。
可以发现一个性质：对于每一个可以这么转移的纵坐标对 \((j', j)\)，要么不在一个连续段，要么恰好有一个点进行了第一种转移。
证明
考虑反证，假设它们都在一个连续段里。
如果他们都没有进行过第一次转移，那转移肯定没有意义。
如果他们都进行过第一次转移，因为他们在同一个连续段里，则它们在第一种转移的输出点为 \((p_{i, j}, j')\) 和 \((p_{i, j}, j)\)。
又，它们的代价为 \(2(j - j') + i > 2(j - j') + p_{i, j}\)，则两个输入点也可以进行第二种转移。则在一开始就有 \(f_{i, j'} = f_{i, j}\)，转移也没有了意义。
根据这个性质，我们可以得知第二种转移的输出点一定是某个 \((i, q_k)\) 或连续段前缀最上方的 \(1\)（因为下面的一定更劣），总共只有 \(\mathcal{O}(n)\) 个。
转移就是从 \(j\) 开始一直跳 \(S\) 的后继进行转移，直到跳的代价超过 \(m\)，可以线段树二分解决，复杂度 \(\mathcal{O}(\log n)\)。
- 横、纵坐标均变大。
则此时的右上角一定是某个 \((i, q_k)\)，因为只有 \(n\) 个这样的转移，所以直接暴力转移即可，是容易的。
考虑如何快速计算。我们可以直接抛弃 \(f\)，而是只滚动的维护 \(g\)。
对于第一种转移，直接将每个连续段的后缀区间赋值成 \(0\) 即可，然后将纵坐标 \(\ge q_1\) 的连续段全部合并成一个 \(i\) 的连续段，类似于一个栈，复杂度显然是 \(\mathcal{O}(n)\) 的。
对于第二种转移，直接对于每个输出点 \((i, j)\)，线段树二分找到最远可以跳到的右端点 \(R\)，将所有 \(j' \in [j, R]\) 的 \(g_{i, j'} \to [j' \in S]\) 即可。
总复杂度 \(\mathcal{O}(n \log n)\)。
代码咕咕咕。