题解：矩形覆盖问题

问题重述

我们有 $N$ 个矩形按顺序放置在一个平面上。每个矩形 $i$ 由其左下角坐标 $(X_i, Y_i)$ 和尺寸 $(A_i, B_i)$ 定义，因此它的坐标范围是 $[X_i, X_i + A_i] \times [Y_i, Y_i + B_i]$。

矩形按照输入顺序依次放置，后放置的矩形可能会覆盖（遮挡）先放置的矩形。如果一个矩形有任何部分被后面的矩形覆盖，它就不能完全暴露在阳光下，因此不能去夏威夷。

我们需要判断每个矩形是否被后面的矩形完全覆盖。如果没有被完全覆盖（即至少有一部分暴露），输出 DA；否则输出 NE。

关键观察

1. 顺序的重要性：矩形按照输入顺序放置，编号 $j > i$ 的矩形可以覆盖编号 $i$ 的矩形，但反之不成立。
2. 完全覆盖与部分覆盖：题目要求矩形完全不被覆盖才能去夏威夷，即只要有任意部分被后面的矩形覆盖，就不能去。
3. 覆盖关系的传递性：如果矩形 $i$ 被矩形 $j$ 覆盖，而矩形 $j$ 又被矩形 $k$ 覆盖，这并不影响矩形 $i$ 被覆盖的事实。

解题思路

朴素方法及其局限性

最直接的方法是对于每个矩形 $i$，检查所有 $j > i$ 的矩形是否与它相交。如果存在至少一个 $j > i$ 与矩形 $i$ 相交，则矩形 $i$ 被覆盖。

这种方法的时间复杂度是 $O(N^2)$，对于 $N \le 10^5$ 来说显然不可行。

高效算法设计

我们需要一个 $O(N \log N)$ 或 $O(N \log^2 N)$ 的算法。核心思想是从后往前处理矩形，并使用合适的数据结构来加速覆盖检查。

核心洞察

考虑从最后一个矩形开始向前处理：

• 当我们处理矩形 $i$ 时，所有 $j > i$ 的矩形都已经被处理过了。
• 我们可以维护一个数据结构，记录所有已处理矩形（即 $j > i$ 的矩形）的覆盖情况。
• 要判断矩形 $i$ 是否被完全覆盖，只需要查询在它的区域内是否被已处理的矩形完全覆盖。

算法框架

1. 坐标离散化：由于坐标范围很大（$10^9$），我们需要将 $x$ 坐标和 $y$ 坐标分别离散化，以便使用线段树等数据结构。

2. 事件驱动扫描：

   • 将每个矩形看作两个事件：一个在 $y = Y_i$（下边界）处矩形"开始"，一个在 $y = Y_i + B_i$（上边界）处矩形"结束"。
   • 按 $y$ 坐标从大到小处理这些事件（相当于从上往下扫描）。

3. 使用线段树维护：

   • 我们使用线段树维护 $x$ 轴上的覆盖情况。
   • 当遇到一个矩形的"上边界"事件（即该矩形的顶部）时，表示我们开始考虑这个矩形。
   • 此时，查询该矩形在 $x$ 轴区间 $[X_i, X_i + A_i]$ 上是否被完全覆盖。
   • 如果完全覆盖，则标记该矩形为被覆盖。
   • 然后将该矩形的 $x$ 区间标记为被覆盖（通过线段树的区间更新）。
   • 当遇到"下边界"事件时，从线段树中移除该矩形的覆盖标记。

4. 从后往前处理：

   • 实际上，由于后放置的矩形会覆盖先放置的矩形，我们应该按矩形的放置顺序反向处理。
   • 也就是说，我们实际上是从最后一个矩形开始，向前处理到第一个矩形。
   • 这样，当我们处理矩形 $i$ 时，所有可能覆盖它的矩形（$j > i$）都已经被加入数据结构中。

算法步骤详解

步骤1：数据准备与离散化

1. 读取所有矩形数据，将每个矩形表示为 $(x_1, y_1, x_2, y_2)$，其中：

   • $x_1 = X_i$, $y_1 = Y_i$（左下角）
   • $x_2 = X_i + A_i$, $y_2 = Y_i + B_i$（右上角）

2. 收集所有 $x$ 坐标（$x_1$ 和 $x_2$）进行离散化：

   • 排序并去重，建立从原始坐标到离散化索引的映射。

步骤2：创建事件列表

对于每个矩形 $i$，创建两个事件：

1. 进入事件：在 $y_2$（矩形顶部）处，类型为"进入"，表示开始考虑这个矩形。
2. 离开事件：在 $y_1$（矩形底部）处，类型为"离开"，表示这个矩形不再影响后续矩形。

这些事件将按 $y$ 坐标从大到小排序（即从上往下扫描）。

步骤3：扫描线处理

初始化一个线段树，用于维护 $x$ 轴上的覆盖情况。线段树的每个节点记录对应区间是否被完全覆盖。

按排序后的事件顺序处理：

1. 遇到"进入"事件（矩形顶部）：

   • 查询该矩形在 $x$ 轴上的区间 $[x_1, x_2]$ 是否被完全覆盖。
   • 如果是，标记该矩形为被覆盖（输出 NE）。
   • 将该矩形的 $x$ 区间标记为被覆盖（更新线段树）。

2. 遇到"离开"事件（矩形底部）：

   • 将该矩形的 $x$ 区间标记为不再被覆盖（更新线段树）。

步骤4：输出结果

按照输入顺序输出每个矩形的结果：如果被标记为被覆盖，输出 NE；否则输出 DA。

算法正确性证明

1. 从后往前处理的正确性：

   • 当我们处理矩形 $i$ 时，所有 $j > i$ 的矩形都已经被处理并加入数据结构。
   • 因此，线段树中记录的就是所有可能覆盖矩形 $i$ 的矩形的覆盖情况。

2. 完全覆盖检查的正确性：

   • 我们检查矩形 $i$ 的整个 $x$ 区间是否被覆盖。
   • 由于我们按 $y$ 坐标从上往下扫描，当遇到矩形 $i$ 的顶部时，所有在它上方（$y$ 坐标更大）的矩形都已经被处理。
   • 如果矩形 $i$ 的整个 $x$ 区间在某个 $y$ 高度上被覆盖，那么它确实被完全覆盖。

3. 事件顺序的重要性：

   • 按 $y$ 坐标从大到小处理确保了我们总是先处理上方的矩形。
   • 这对于覆盖检查是必要的，因为上方的矩形会覆盖下方的矩形。

时间复杂度分析

1. 离散化：$O(N \log N)$
2. 事件排序：$O(N \log N)$
3. 扫描线处理：每个事件涉及线段树的更新或查询，每次操作 $O(\log N)$，总共 $O(N \log N)$

总时间复杂度：$O(N \log N)$，可以处理 $N = 10^5$ 的数据规模。

空间复杂度分析

1. 存储矩形数据：$O(N)$
2. 离散化坐标：$O(N)$
3. 线段树：$O(N)$
4. 事件列表：$O(N)$

总空间复杂度：$O(N)$。

总结

本题的关键在于将二维的矩形覆盖问题转化为一维的区间覆盖问题，通过从后往前处理和扫描线技术，结合线段树等高效数据结构，将时间复杂度从 $O(N^2)$ 优化到 $O(N \log N)$。

核心技巧：

1. 从后往前处理：利用矩形按顺序放置的特性
2. 扫描线算法：将二维问题降为一维问题
3. 坐标离散化：处理大范围坐标
4. 线段树：高效维护区间覆盖信息

这种从后往前处理结合扫描线的方法，是解决类似矩形覆盖问题的经典技巧，在计算几何和竞赛编程中有着广泛的应用。