题解 | #校门外的树#

这是一道区间覆盖去重的计数问题，核心是计算施工区域（可能重叠）总共移除的树的数量，再用初始总树数减去该数量得到剩余树数。

解题思路一：集合法

1. 初始树数计算：马路长度为L，从0到L的每个整数点都有树，因此初始总树数为 L + 1。
2. 标记移除区域：用集合（自动去重）记录所有施工区域覆盖的位置，避免重复统计重叠区域的树。
3. 计算剩余树数：初始总树数减去被移除位置的数量，得到最终剩余树数。

代码实现

# 读取马路长度L和施工区域数M
L, M = map(int, input().split())

# 用集合存储被移除的树的位置（自动去重）
removed = set()

# 遍历每个施工区域，标记移除的位置
for _ in range(M):
    l, r = map(int, input().split())
    # 将区间[l, r]内的所有位置加入集合
    for pos in range(l, r + 1):
        removed.add(pos)

# 初始总树数 - 被移除的树数 = 剩余树数
remaining = (L + 1) - len(removed)
print(remaining)

解题思路二：数组法

思路分析

1. 初始化数组：创建一个长度为 L + 1 的数组 trees，并将所有元素初始化为 0。这个数组的每个下标 i 代表马路上位置为 i 的那棵树。0 表示这棵树没有被移除。
2. 标记施工区域：遍历每一个施工区域 [l, r]。对于这个区间内的每一个位置 i（从 l 到 r），我们将数组 trees 中对应的元素 trees[i] 的值加 1。这表示位置 i 的树被移除了（加 1 可以表示被覆盖了一次，即使多个区域重叠，值会大于 1，但我们只关心它是否被覆盖过）。
3. 统计剩余树木：最后，遍历整个 trees 数组，统计值为 0 的元素的个数。这个个数就是没有被任何施工区域覆盖的树的数量，也就是题目要求的答案。

代码实现（Python）

# 读取马路长度 L 和施工区域数 M
L, M = map(int, input().split())

# 1. 初始化数组，长度为 L+1，所有元素为 0
# trees[i] = 0 表示位置 i 的树未被移除
trees = [0] * (L + 1)

# 2. 标记施工区域
for _ in range(M):
    l, r = map(int, input().split())
    # 遍历区间 [l, r] 内的每一个位置
    for i in range(l, r + 1):
        # 将该位置标记为被移除（加 1）
        trees[i] += 1

# 3. 统计剩余的树的数量（即数组中值为 0 的元素个数）
remaining_trees = 0
for is_removed in trees:
    if is_removed == 0:
        remaining_trees += 1

print(remaining_trees)

方法对比与思考