题意

数轴 0..l 的每个整数点都有一棵树。给出 m 个闭区间 [u, v]，这些区间内的树都要移走，包含端点。问最后还剩多少棵树。

思路

直接做法是开一个布尔数组，遇到区间就把区间内所有位置标记为删除。本题这样也能通过。

这里用差分写法来练习“区间修改，最后统一统计”：

• 在 left 位置让覆盖数加一；
• 在 right + 1 位置让覆盖数减一。

处理完所有区间后，从 0 到 l 做前缀和。当前覆盖数 covered 为 0，说明这个位置没有被任何删树区间覆盖，答案加一。

旧目录中保留了 C++ 直接标记版本；Python 教学版使用列表实现差分，不新增 brute.py。

Python 知识

• /home/rainboy/mycode/hugo-blog/content/program_language/python/input_output_and_strings.md：用 map(int, input().split()) 读取每行两个整数。
• /home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：本题是第一行两个整数，后面 m 行区间的常见格式。
• [0] * (length + 2) 创建差分列表，多开一位用于 right + 1。
• for _ in range(interval_count): 表示只关心循环次数，不使用循环变量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18length, interval_count = map(int, input().split())

diff = [0] * (length + 2)

for _ in range(interval_count):
    left, right = map(int, input().split())
    diff[left] += 1
    diff[right + 1] -= 1

covered = 0
answer = 0

for position in range(length + 1):
    covered += diff[position]
    if covered == 0:
        answer += 1

print(answer)

Pythonic 写法

差分数组：

1
2
3
4
5
6
7
8
9
10
11L, m = map(int, input().split())
diff = [0] * (L + 2)
for _ in range(m):
    l, r = map(int, input().split())
    diff[l] += 1
    diff[r + 1] -= 1
cover = answer = 0
for i in range(L + 1):
    cover += diff[i]
    answer += cover == 0
print(answer)

复杂度

处理区间需要 $O(m)$，扫描所有树的位置需要 $O(l)$，总时间复杂度是 $O(l+m)$，空间复杂度是 $O(l)$。

总结

这题既能直接标记，也很适合作为差分入门：区间删除不必逐点处理，只改两个边界，最后统一前缀扫描。