题解

问题分析

题目要求用最少的防御塔覆盖整个矩形城池（左下角$(0,0)$，右上角$(n+1,n+1)$）。防御塔分为4个方向，分别覆盖特定的矩形区域：

• 方向1（RU）：覆盖$(a \ge x_i, b \ge y_i)$（右上区域）
• 方向2（LU）：覆盖$(a \le x_i, b \ge y_i)$（左上区域）
• 方向3（LD）：覆盖$(a \le x_i, b \le y_i)$（左下区域）
• 方向4（RD）：覆盖$(a \ge x_i, b \le y_i)$（右下区域）

核心挑战是找到最少的防御塔组合，使得城池内所有点均被至少一个塔覆盖。

关键洞察

1. 覆盖范围的互补性：单个方向的防御塔无法覆盖整个矩形，需组合不同方向的塔。例如，RU（右上）和LD（左下）的覆盖范围可能互补，LU（左上）和RD（右下）可能互补。
2. 最优塔的选择：对于每个位置，需选择覆盖范围最大的防御塔。例如，对RU塔，相同$x$下$y$越小，覆盖的右上区域越大。
3. 对称性：4个方向存在旋转对称性（如交换$x/y$、翻转坐标可将一个方向转化为另一个），可通过旋转变换复用同一套逻辑处理所有方向组合。

算法步骤

1. 预处理最优防御塔：

   • 对LU塔（方向2）：计算每个$x$位置上最小的$y_i$（记为yl[x]），确保$b \ge y_i$的覆盖范围最大。
   • 对RD塔（方向4）：计算每个$x$位置上最大的$y_i$（记为yr[x]），并通过前缀最大值优化，快速获取$x \le i$时的最大覆盖范围。
   • 对RU塔（方向1）：计算每个$x$位置上$y_i$最小的塔（记为pd[x]），通过前缀优化获取$x \le i$时的最优RU塔。
   • 对LD塔（方向3）：计算每个$y$位置上$x_i$最大的塔（记为pr[y]），通过后缀优化获取$y \ge i$时的最优LD塔。

2. 构建依赖关系图：

   • 分析RU塔与LD塔的配合关系：若RU塔$i$和LD塔$j$能共同覆盖部分区域，则建立从$j$到$i$的边。
   • 通过DFS计算覆盖所需的最少塔数（f数组存储到达每个塔的最少塔数）。

3. 对称性处理：

   • 对城池进行4次旋转变换（交换$x/y$、翻转坐标、调整方向），每次变换后复用上述逻辑计算最优解，确保覆盖所有可能的方向组合。

4. 结果整合：

   • 从4次旋转处理的结果中取最小值，若无法覆盖则输出Impossible。

代码解析

• 快速读入：使用FastRead模块处理大规模输入，提高效率。
• 预处理数组：yl、yr、pd、pr分别存储各方向最优塔的信息，通过前缀/后缀优化实现快速查询。
• 图与DFS：Add函数构建塔之间的依赖边，DFS计算覆盖所需的最少塔数，f数组记录中间结果。
• 旋转变换：Solve函数中4次循环处理旋转后的场景，通过坐标变换和方向调整复用Work函数的逻辑。

复杂度分析

• 时间复杂度：$O(T \cdot n)$，其中$T$为测试组数，$n$为防御塔数量。预处理和DFS均为线性扫描，旋转变换不增加额外复杂度。
• 空间复杂度：$O(n)$，用于存储预处理数组、图的边和中间结果。

综上，该算法通过贪心选择最优防御塔、构建依赖关系图和利用对称性，高效求解了最少防御塔覆盖问题。