题解

问题分析

题目要求用最少的防御塔覆盖整个矩形城池（左下角$(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$、翻转坐标可将一个方向转化为另一个），可通过旋转变换复用逻辑处理所有方向组合。
4. 依赖关系：部分塔的覆盖需要其他塔的配合，可通过图建模这种依赖，用DFS计算最少塔数。

算法步骤

1. 预处理最优防御塔：
   针对每个方向，筛选出覆盖范围最大的塔，并通过前缀/后缀优化快速查询：

   • LU塔（方向2）：用yl[x]记录$x$处最小的$y$（$y$越小，覆盖的左上区域越大），并做后缀优化（从右到左取最小值）。
   • RD塔（方向4）：用yr[x]记录$x$处最大的$y$（$y$越大，覆盖的右下区域越大），并做前缀优化（从左到右取最大值）。
   • RU塔（方向1）：用pd[x]记录$x$处$y$最小的塔（$y$越小越好），并做前缀优化。
   • LD塔（方向3）：用pr[y]记录$y$处$x$最大的塔（$x$越大越好），并做后缀优化。

2. 构建依赖关系图：
   分析RU与LD塔的配合关系：若RU塔$i$和LD塔$j$能共同覆盖部分区域，则直接标记$i$的最少塔数为2；否则建立从$j$到$i$的边（表示$i$依赖$j$）。通过DFS遍历图，更新每个塔所需的最少塔数（f数组）。

3. 对称性处理：
   对城池进行4次旋转变换（交换$x/y$、翻转$x$坐标、调整方向），每次变换后复用Work函数的逻辑，处理所有可能的方向组合，确保覆盖所有互补情况。

4. 结果计算：
   从4次变换的结果中取最小值，若仍为无穷大则输出“Impossible”，否则输出最少塔数。

代码解析

• 快速读入：FastRead模块处理大规模输入，提高效率。
• 预处理数组：yl、yr、pd、pr分别存储各方向最优塔的信息，前缀/后缀优化使其支持$O(1)$查询。
• 图与DFS：Add函数构建塔之间的依赖边，DFS通过遍历依赖关系更新f数组（记录覆盖所需的最少塔数）。
• 旋转变换：Solve函数中4次循环通过坐标变换（swap(x,y)、x = n - x + 1）和方向调整（d = (d & 3) + 1），复用Work函数处理所有对称情况。
• 结果整合：最终ans取4次变换的最小值，加2（基础组合的塔数）后输出，若无法覆盖则输出“Impossible”。

复杂度分析

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

综上，算法通过贪心选择最优塔、利用对称性减少计算量、结合图论处理依赖关系，高效求解了最少防御塔覆盖问题，适用于大规模输入。