题解：AT_abc408_c [ABC408C] Not All Covered

_peter6 · 2025-12-05 11:11:53 · 题解

问题

题目要求找到最少需要摧毁的炮塔数量，使得至少有一堵城墙没有被任何炮塔守卫。本质上是：

• 先判断是否存在天然未被守卫的城墙。
• 若所有城墙都被守卫，则找到被最少炮塔覆盖的那堵城墙，摧毁这些炮塔即可让该城墙无守卫。

思路

由于 N 最大为 10^6，M 最大为 2 \times 10^5，直接暴力统计每堵城墙的覆盖数会超时，因此使用差分数组高效计算区间覆盖数。

code