C. 冒险家 详细题解

问题重述

平面上有 $n$ 个点（可能重合）。要选择一个分割点 $(x_0, y_0)$，将平面分成四个象限（包含边界）：

• 第一象限（含右、上边界）：$x \ge x_0,\ y \ge y_0$
• 第二象限（含左、上边界）：$x < x_0,\ y \ge y_0$
• 第三象限（含右、下边界）：$x \ge x_0,\ y < y_0$
• 第四象限（含左、下边界）：$x < x_0,\ y < y_0$

记四个象限内的点数分别为 $c_1,c_2,c_3,c_4$。目标：最大化 $m = \min(c_1,c_2,c_3,c_4)$，并输出任意一个达到该最大值的 $(x_0,y_0)$。

核心观察

• 最优的 $x_0$ 可以取在某个点的 $x$ 坐标处（或稍向左/右），因为移动 $x_0$ 只改变点在左右的分组，且只有在穿过点的 $x$ 坐标时才会改变计数。同样 $y_0$ 可以取在某个点的 $y$ 坐标处。
• 因此，我们可以枚举可能的 $x_0$（所有不同的 $x$ 坐标），然后对于每个 $x_0$，快速找到最优的 $y_0$ 使得 $\min(c_1,c_2,c_3,c_4)$ 最大。
• 问题转化为：给定一个垂直线 $x = x_0$ 将点分为左右两部分，我们需要在 $y$ 轴上找一个分割点 $y_0$，使得四个象限的点数都不小于某个值 $k$。

二分答案

显然答案 $k$ 满足 $0 \le k \le \lfloor n/4 \rfloor$，且可以二分。假设我们判断是否存在 $(x_0,y_0)$ 使得四个象限的点数都 $\ge k$。

固定 $k$，对于每个可能的 $x_0$（即所有点的 $x$ 坐标），我们检查是否存在 $y_0$ 满足：

• 左侧部分（$x < x_0$）中，$y \ge y_0$ 的点数 $\ge k$ 且 $y < y_0$ 的点数 $\ge k$；
• 右侧部分（$x \ge x_0$）中，$y \ge y_0$ 的点数 $\ge k$ 且 $y < y_0$ 的点数 $\ge k$。

由于左右两部分独立，我们可以分别求出每个部分中 $y_0$ 的可行区间，然后判断是否有交集。

数据结构维护

对 $y$ 坐标离散化后，我们可以用线段树维护点数的前缀和。但这里需要支持动态删除左侧的点（当 $x_0$ 向右移动时）。

算法流程：

1. 将所有点按 $x$ 坐标排序。

2. 预处理一个数据结构（如 Fenwick 树或线段树）存储所有点的 $y$ 坐标计数，初始时包含所有点（对应 $x_0$ 为最左侧的情况）。

3. 枚举 $x_0$ 的取值（所有不同的 $x$ 坐标，按升序）：

   • 当前数据结构中存储的是 $x \ge x_0$ 的点（右侧部分）。左侧部分就是已经移除的点。
   • 对于当前右侧部分的 $y$ 分布，我们可以通过线段树查询得到：对于任意 $y_0$，右侧部分中 $y \ge y_0$ 和 $y < y_0$ 的点数。类似地，左侧部分我们也可以用一个额外的数据结构（或者维护前缀和）来查询。
   • 我们需要找到 $y_0$ 使得左右两侧的上下计数都 $\ge k$。这等价于：左侧部分中，$y_0$ 必须落在某个区间 $[L_l, R_l]$ 内（即左侧部分的累积分布函数满足要求）；右侧部分中，$y_0$ 必须落在区间 $[L_r, R_r]$ 内。如果两个区间有交集，则存在可行的 $y_0$。
   • 为了快速得到这些区间，可以在线段树上进行二分（或递归下降）。标程中的 FindBest 函数正是做这件事：它在线段树上递归，同时维护左右两侧的计数，最终找到使最小点数最大的 $y_0$，并返回该最大最小值。

4. 当 $x_0$ 向右移动到下一个值时，将当前 $x$ 坐标上的所有点从右侧数据结构中删除（并添加到左侧的计数中）。

复杂度

• 排序 $O(n \log n)$。
• 对于每个不同的 $x$ 坐标，需要 $O(\log n)$ 的时间在线段树上找到可行区间（或最优 $y_0$）。
• 总复杂度 $O(n \log^2 n)$（因为二分答案外层还有一个 $\log$），但标程直接在一个扫描中同时找到了最大 $k$，不需要外层二分，实际实现为 $O(n \log n)$ 或 $O(n \log^2 n)$。由于 $n \le 10^5$，可接受。

标程解析

标程中的关键数据结构：

• Tree 是动态开点的线段树，每个节点维护一个 Count 结构，包含 left 和 right 两个整数，表示在该节点对应的 $y$ 区间内，小于当前分割点（递归过程中临时设定的 $y_0$）的点数和大于等于当前分割点的点数。递归函数 FindBest 不断下探，最终得到最优的 $y_0$ 和对应的最小象限点数。
• 扫描过程中，维护一个全局的 Tree，初始包含所有点。随着垂直线右移，将左侧的点从树中移除（Remove 操作）。每次移除一批点后，调用 FindBest 更新答案。

该实现巧妙地同时处理了左右两侧的计数，因为左侧的点已经被移除，而 FindBest 在递归时通过参数 left 和 right 传递了左侧部分在当前 $y$ 区间内的点数，从而实现了左右合并。

算法步骤总结

1. 读入所有点，按 $x$ 排序。
2. 建立动态开点线段树，将所有点的 $y$ 坐标插入。
3. 初始化答案 $k=0$，最优坐标 $(bx,by)$。
4. 从左到右扫描不同的 $x$ 值（即所有点的 $x$ 坐标）：
   • 调用 FindBest 函数，在当前线段树（代表右侧部分）中递归寻找最优水平分割线，同时通过传递的左右计数参数得到左侧部分的信息，计算出当前 $x_0$ 下能达到的最大最小象限点数 $cur$。
   • 如果 $cur > k$，更新 $k$ 和 $(bx,by) = (当前 x, 找到的 y_0)$。
   • 然后将当前 $x$ 坐标上的所有点从线段树中移除（相当于将它们划归左侧）。
5. 输出 $k$ 和 $(bx,by)$。

复杂度

• 线段树节点数 $O(n \log N)$，其中 $N$ 是 $y$ 坐标值域大小（使用动态开点，实际节点数约 $O(n \log C)$，$C=2\times 10^9$）。
• 每个点插入和删除一次，每次 $O(\log C)$。
• FindBest 每调用一次 $O(\log C)$。
• 总复杂度 $O(n \log C)$，在给定约束下可以接受。

参考代码（标程已提供）

标程的代码即为本题的正解，使用动态开点线段树和递归搜索实现。可直接使用。

总结

本题的核心在于将二维问题转化为一维扫描，利用线段树维护 $y$ 方向上的分布，并通过递归搜索快速找到最优水平分割线。二分答案可省略，因为扫描过程中自然就能得到最大 $k$。