题解

1. 核心问题回顾

箱子可移除的条件：其东北角(rx[i], ry[i])的南侧（y < ry[i]）和西侧（x < rx[i]）无任何未移除的箱子。代码通过分治、数据结构和拓扑排序分别处理两种模式。

2. 关键数据结构与函数解析

（1）树状数组（BIT）

• 功能：维护y坐标的计数，支持单点更新（添加/删除箱子的y坐标）和前缀查询（统计y ≤ 目标值的箱子数量）。
• 应用场景：模式2中判断“箱子i的东北角左下区域是否有其他箱子”——若查询y < ry[i]的数量大于0，则i被阻挡。

（2）分治函数（build 与 solve0）

分治是代码的核心思想，将坐标区间拆分为左右两部分，仅处理“左半区间箱子对右半区间箱子的阻挡关系”，避免O(N²)的暴力枚举。

• build 函数（模式1）：构建DAG的分治树

  1. 将x坐标范围[0, 2N-1]分治为[l, mid]和[mid+1, r]。
  2. 左半区间收集“箱子的西南角y坐标（ly[i]）”，右半区间收集“箱子的东北角y坐标（ry[i]）和西南角y坐标（ly[i]）”。
  3. 对两类y坐标排序，通过双指针匹配左半区间箱子对右半区间箱子的阻挡关系，构建中间节点（分治树节点）和箱子节点的依赖边。
  4. 递归处理左右子区间，最终形成完整的DAG。

• solve0 函数（模式2）：离线判断每个箱子是否可在初始时移除

  1. 将箱子集合分治为[l, mid]和[mid+1, r]。
  2. 收集左半区间箱子的(rx[i], ry[i])（东北角坐标，用于判断是否阻挡右半区间）和右半区间箱子的(lx[i], ly[i])（西南角坐标，用于判断是否被阻挡）。
  3. 按x坐标升序排序所有收集的坐标，依次处理：
     • 遇到左半区间箱子：查询树状数组中y < ry[i]的数量，若大于0则该箱子被阻挡（ans[i] = false）。
     • 遇到右半区间箱子：将其ly[i]加入树状数组（标记该y坐标存在）。
  4. 回溯清理树状数组，递归处理左右子区间。

（3）模式1具体逻辑（solve1 函数）

• 步骤1：初始化：重置DAG的边和入度数组，将箱子的lx[i]（西南角x）和rx[i]（东北角x）映射到分治区间的对应位置（bell和belr数组）。
• 步骤2：构建DAG：调用build函数生成分治树和依赖边，中间节点用于传递“阻挡关系的层级依赖”。
• 步骤3：拓扑排序：
  1. 将入度为0的节点（初始可处理的中间节点或箱子）加入队列。
  2. 弹出节点，若为箱子节点则输出其编号（+1，因代码中箱子编号从0开始）。
  3. 遍历该节点的出边，减少对应节点的入度，入度为0则加入队列。
  4. 最终输出的序列即为合法的移除顺序。

（4）模式2具体逻辑（solve2 函数）

• 步骤1：初始化：默认所有箱子均可初始移除（ans[i] = true）。
• 步骤2：分治判断：调用solve0函数，通过分治和树状数组离线判断每个箱子是否被其他箱子阻挡。
• 步骤3：输出结果：遍历ans数组，输出1（可移除）或0（不可移除），形成二进制字符串。

3. 复杂度分析

• 时间复杂度：两种模式均为O(N log²N)。分治共O(logN)层，每层排序和树状数组/双指针操作均为O(N logN)，整体复杂度符合N ≤ 1e5的约束。
• 空间复杂度：O(N logN)。模式1中DAG的边数和中间节点数为O(N logN)，模式2中树状数组和分治临时数组为O(N)。

4. 代码关键细节说明

• 坐标转换：代码中将输入的坐标减1（lx[i]--等），将坐标范围从[1, 2N]转为[0, 2N-1]，避免树状数组查询时的边界问题。
• 中间节点作用：模式1的分治树中间节点用于“聚合”同一层级的阻挡关系，确保依赖边的数量可控（避免O(N²)边），使拓扑排序高效运行。
• 回溯清理：模式2的solve0函数中，处理完一个分治层级后需清理树状数组的修改，避免影响其他分治分支的判断。