如何用分治法添加n log n块石子实现网格优美排列？算法问询

我们有一个10^9×109的网格，已放置n个坐标互不相同的石子（2≤n≤2×10^4），当前排列不满足优美排列的要求。优美排列的定义是：任意两个石子必须满足以下条件之一：

• 处于同一行（y₁=y₂）；
• 处于同一列（x₁=x₂）；
• 存在第三个石子位于二者构成的矩形范围内，即满足 min(x₁,x₂) ≤ x₃ ≤ max(x₁,x₂) 且 min(y₁,y₂) ≤ y₃ ≤ max(y₁,y₂)。

允许添加至多n log n块新石子，新石子坐标必须是整数且不能与已有石子（包括初始和新增的）重复，初始石子位置固定。需要输出添加的石子数量及坐标。

已知分治法适用于该问题，但难以设计出O(n log n)时间复杂度的高效方案，寻求思路或已有算法。

核心逻辑 #

分治法的核心是将点集按x坐标递归拆分，先让每个子点集成为优美排列，再通过添加少量石子在拆分边界构建「桥接」，保证跨子集合的任意点对满足优美条件。整个过程的时间复杂度为O(n log n)，添加的石子数不超过O(n log n)（实际远低于上限）。

具体实现步骤 #

1. 排序与递归拆分

• 先将所有石子按x坐标从小到大排序（x相同时按y坐标排序），确保拆分后的子集合大小尽可能均衡。
• 取排序后中间位置的石子x坐标作为mid_x，将点集拆分为左子集合S_L（x ≤ mid_x）和右子集合S_R（x > mid_x）。
• 递归处理两个子集合，直到子集合大小≤2：
  • 若子集合大小为1：无需处理，单个点天然满足优美条件。
  • 若子集合大小为2：设两点为P₁(x₁,y₁)、P₂(x₂,y₂)。若二者同行或同列，直接满足条件；否则，添加点(x₁,y₂)（若该坐标已存在，则替换为(x₂,y₁)）——此时P₁与新点同列，P₂与新点同行，且新点位于P₁和P₂的矩形范围内，完全满足优美要求。

2. 子集合合并（桥接构建）

当左右子集合都处理为优美排列后，需要保证跨集合的任意点对满足条件：

• 提取S_L的y坐标极值（最小y_L_min、最大y_L_max），提取S_R的y坐标极值（最小y_R_min、最大y_R_max）。
• 在x=mid_x这条竖线上，添加四个石子：(mid_x, y_L_min)、(mid_x, y_L_max)、(mid_x, y_R_min)、(mid_x, y_R_max)（添加前需检查坐标是否重复，若重复则微调y值，比如±1，网格空间足够支持）。
• 有效性说明：
  • 对于S_L内的任意点，由于S_L是优美集合，它必然与y_L_min或y_L_max对应的点满足优美条件，而新添加的(mid_x, y_L_min)与该点同列，因此S_L内任意点与这个新点满足优美条件。同理，S_R内任意点与(mid_x, y_R_min)或(mid_x, y_R_max)满足优美条件。
  • 对于跨集合的点对P∈S_L、Q∈S_R：
    • 若二者同行或同列，直接满足条件；
    • 否则，它们的矩形x范围必然包含mid_x，y范围必然包含y_L_min/y_L_max或y_R_min/y_R_max中的至少一个，因此对应的新添加石子就在矩形范围内，满足条件3。

3. 复杂度验证

• 时间复杂度：排序耗时O(n log n)，递归每层处理的点总数为n，共O(log n)层，总时间为O(n log n)。
• 添加石子数：每层递归最多添加4个石子，总层数O(log n)，总添加数为O(n log n)（实际为4*(n-1)，远低于题目限制的n log n）。

关键注意事项 #

• 每次添加石子前必须检查坐标是否已存在（包括初始石子和已添加的石子），若重复则微调坐标（如y值±1），由于网格规模为10^9×109，不会出现无坐标可用的情况。
• 递归拆分时若遇到大量x坐标相同的点，可切换为按y坐标中位数拆分，保证子集合大小均衡，避免递归深度退化。

内容的提问来源于stack exchange，提问作者user22858842