[NOIP 2005 普及组] 校门外的树

题意

数轴 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): 表示只关心循环次数，不使用循环变量。

代码

python

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)

Guide 风格代码

cppbook《C++ 快速入门》教学风格的写法（std:: 前缀、i += 1 循环、0 起始下标）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-08-14 15:18
 * update_at: 2026-08-14 15:18
 */
/* P1047 校门外的树：布尔数组记录每个位置是否被移走，最后统计留在原处的树。 */

#include <iostream>

int main() {
    const int max_length = 10000;  // 路的长度最大为 10000

    int road_length, zone_count;
    std::cin >> road_length >> zone_count;

    bool removed[max_length + 1];  // removed[i] = true 表示位置 i 的树被移走
    for (int i = 0; i <= road_length; i += 1) {
        removed[i] = false;
    }

    // 施工区间 [left, right] 内的树逐点标记为移走，区间包含端点
    for (int k = 0; k < zone_count; k += 1) {
        int left, right;
        std::cin >> left >> right;
        for (int i = left; i <= right; i += 1) {
            removed[i] = true;
        }
    }

    // 统计没有被移走的树
    int answer = 0;
    for (int i = 0; i <= road_length; i += 1) {
        if (!removed[i]) {
            answer += 1;
        }
    }

    std::cout << answer << '\n';
    return 0;
}

Pythonic 写法

差分数组：

python

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)$ 。

总结

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