语言月赛 202410 校门外的施工
题目分析
- 有 $m$ 棵树和 $m-1$ 片草坪，排列为：树 $1$，草坪 $1$，树 $2$，草坪 $2$，$\ldots$，树$m$；
- 两种施工操作破坏区间内的绿化：
- 类型 $1$：破坏第 $l$ 棵树和第 $r$ 棵树之间（不含 $l,r$）的所有绿化，即破坏树 $(l+1)$ 到 $(r-1)$ 和草坪 $l$ 到 $r-1$；
- 类型 $2$：破坏第 $l$ 棵树和第 $r$ 棵树之间（包含 $l,r$）的所有绿化，即破坏树 $l$ 到 $r$ 和草坪 $l$ 到 $r-1$；
- 施工后统计剩余未被破坏的树和草坪数量。
解题思路
- 维护两个数组：
tree[1,.., m] 标记每棵树是否被破坏（0 表示存活，1 表示被破坏）；grass[1,.., m - 1] 标记每片草坪是否被破坏；- 两个数组初始化均设为全局变量即可。
- 对每次施工，根据类型更新
tree 和 grass 的状态；
- 最后分别统计两个数字里
0 的个数即为剩余的树和草坪数。
实现步骤
- 初始化
tree 和 grass 数组，全部标记为 0；
- 遍历每次施工：
- 若类型为 $1$：
- 对树：标记
tree[l + 1, .., r - 1] 为 1（若区间非空）；
- 对草坪：标记
grass[l, .. ,r - 1] 为 1；
- 若类型为 $2$：
- 对树：标记
tree[l, .., r] 为 1；
- 对草坪：标记
grass[l, .., r - 1] 为 1；
- 统计
tree 中 0 的数量为剩余树数，统计 grass 中 0 的数量为剩余草坪数；
- 输出两个结果。
复杂度分析
- 每次施工最多修改 $O(m)$ 个元素，最多 $n$ 次操作；
- 时间复杂度为 $O(m \times n)$，对于 $m,n \leq 5000$ 可接受；
- 空间复杂度为 $O(m)$。
总结
- 题目考察区间标记和状态维护；
- 注意边界处理和区间是否包含端点的区别；
- 通过简单数组标记和统计实现，代码逻辑直观。