题目大意
二维平面上有 $n+1$ 个点，编号为 $0$ 到 $n$，第 $i$ 个点的坐标为 $(x_i,y_i)$，保证第 $0$ 个点的坐标为 $(0,0)$。你有一个矩形，初始时其为仅包含点 $(0,0)$ 的退化矩形。每次操作，你可以从平面上的 $n+1$ 个点中选择任意一个未被矩形包含的点，并将矩形扩大直到恰好包含该点。
定义一次操作的代价为，新得到的矩形的周长中，不与原矩形重合的部分的长度。给定所有点，和一个代价上限 $m$，求出是否存在一种操作方案，使得最终矩形包含所有 $n+1$ 个点，且每一次操作的代价均不超过 $m$。
数据范围
多组测试，所有测试数据的 $n$ 总和不超过 $5\times 10^5$。代价上限 $m$ 满足 $1\leq m\leq 4\times 10^9$，点的坐标 $(x_i,y_i)$ 满足 $1\leq x_i,y_i\leq 10^9$。
解题过程
由于坐标范围较大，首先将坐标离散化为 $O(n)$ 级别。
对于此类数据范围较大的题目，我们常常考虑动态规划。令 $f(x,y)$ 表示是否存在某种操作方案可以得到左下角为 $(0,0)$，右上角为 $(x,y)$ 的矩形，若存在则 $f(x,y)=1$，否则 $f(x,y)=0$。转移时枚举下一步操作选择的点 $(x_i,y_i)$，检查代价是否超过上限 $m$，并从 $f(x,y)$ 转移到 $f(\max(x,x_i),\max(y,y_i))$。该朴素动态规划的时间复杂度为 $O(n^3)$。
考虑对转移部分进行优化。我们可以将转移分为三类：
- $x_i > x$ 且 $y_i > y$；
- $x_i > x$ 且 $y_i\leq y$；
- $x_i\leq x$ 且 $y_i>y$。
其中第二和第三类转移是对称的。
对于第一类转移，从 $f(x,y)$ 转移到 $f(x_i,y_i)$ 的操作代价为 $2x_i+2y_i-x-y$，我们可以定义辅助数组 $g(x,y)$ 表示，所有满足 $x'
对于第二类转移，从 $f(x,y)$ 转移到 $f(x_i,y)$ 的操作代价为 $2x_i+y-2x$。令 $h_1(x,y)$ 表示最大的 $x'
转移中涉及到的辅助数组均可以在转移过程中以 $O(n^2)$ 的时间复杂度维护，此时得到的做法时间复杂度为 $O(n^2)$。
由于 $n$ 的上限为 $5\times 10^5$，而动态规划的状态数量已经达到了 $O(n^2)$ 级别，这启发我们考虑在对 $x$ 轴扫描线的过程中，使用数据结构对于每个 $y$ 维护 $f(x,y)$ 的值。由于操作代价的单调性，我们只需要实时维护 $p_y$ 表示当前最大的 $x'$ 满足 $f(x',y)=1$。
在从 $x-1$ 移到 $x$ 的过程中，我们首先进行第二类转移。设 $y_{\min}$ 为所有横坐标为 $x$ 的输入点中纵坐标的最小值。对于每个 $y\geq y_{\min}$，我们尝试用第二类转移更新 DP 值。但是目前维护的信息不适合线段树，且无法在低于 $O(n^2)$ 的时间内找出所有需要更新的位置，我们分析性质并且给出引理：
引理：若某个 $y\geq y_{\min}$ 在某次无法被第二类转移更新 DP 值，则直到该纵坐标在之后的某个时刻被第一或三类转移更新 DP 值之前，忽略该纵坐标不影响任何一类转移。
证明：由于第三类转移是在某个横坐标内部转移，则显然在该纵坐标 DP 值被重新更新为 $1$ 之前不能参与任何第三类转移。对于第二类转移，由于其是在该纵坐标内部转移，且操作代价具有单调性，故若当前不能转移，则在 $p_y$ 被更新之前不能参与任何第二类转移。对于第一类转移，设某个需要被转移到的输入点为 $(x',y')$，由于当前不能进行转移，代价 $y+2x-2p_y>m$，而该第一类转移的代价为 $2x'+2y'-p_y-y$，由 $x'\geq x,y'\geq y$ 可知该代价也大于 $m$，故这样的转移不成立。
由引理可知，如果线段树中只维护未被忽略的位置，则所有位置的 $p_y$ 关于 $y$ 单调不降。于是我们可以维护所有 $p_y$ 的单调栈，每次将 $\geq y_{\min}$ 的一段后缀的 $p_y$ 更新为 $x$，同时每弹出一段相同 $p_y$ 的区间，它们进行第二类转移的代价是关于 $y$ 单调增的一次函数，我们可以找出其中不能转移的部分，将那段区间的信息在线段树上清空，剩余部分的信息保留。这部分的时间复杂度为 $O(n)$ 次线段树操作。
然后我们进行第一类转移。枚举所有横坐标为 $x$ 的输入点，在线段树上区间查询 $y+p_y$ 的最大值，判断可不可以转移即可。注意到输入点的 $y$ 值一定不会小于 $y_{\min}$，所以第一类转移不影响单调栈中的信息。
然后我们进行第三类转移。对于每个 $x$ 坐标，我们只需要考虑三小类转移：
- 以某个第一类转移中更新到的输入点为起点的转移；
- 以某个 $x_{\min}=x$ 的纵坐标为起点的转移；
- 在单调栈被更新之前，跨过原单调栈的两段的转移。
不属于这三小类中任意一种的位置满足：在那一段对应的横坐标 $p_y$ 时就有同样的 DP 值，该横坐标同样可以进行第三类转移，即 $x_{\min}\leq p_y$。而由于代价的单调性，若在当前 $x$ 可以转移，则早应在横坐标 $p_y$ 处已经进行了转移，故这样的转移是可以忽略的。
这三小类转移的数量总数是 $O(n)$ 级别的。每次转移的时候，在线段树上维护的所有 $x_{\min}\leq x$ 的位置中，二分出第一个距离过远而无法转移的，并将 DP 值区间覆盖为 $1$ 即可。
所有上述的转移，操作，与需要维护的信息均可以用线段树在 $O(\log n)$ 的时间内完成，具体的实现细节略过不提。
时间复杂度 $O(n\log n)$。