解题思路

马路上的树种在位置 0 到位置 l，一共有 l+1 棵。

题目要我们把一些区域里的树移走，再数一数还剩下多少棵。注意：区域可能会重叠！如果直接算“总树数 - 每个区域的长度”，重叠的部分会被减掉两次，答案就错了。

所以我们用一个“标记数组” b 来帮忙：

1. b[i] = 0 表示位置 i 的树还在；
2. b[i] = 1 表示位置 i 的树被移走了；
3. 每个区域 [u, v] 就把它里面的每一个位置都标成 1；
4. 最后从 0 数到 l，统计 b[i] == 0 的位置有多少个，剩下的树就是这个数量。

因为标记法是一棵一棵树地做标记，区域再怎么重叠，都不会重复“扣树”，这就是它比直接相减更安全的原因。

参考代码

// P4440 校门外的树：用标记数组统计被移走的树，再数剩下的树
#include <iostream>
using namespace std;

int a[1000005];  // a[i]=1 表示位置 i 的树被移走（放全局，数组大不占栈）

int main() {
    int l, m;
    cin >> l >> m;          // l 是马路长度，m 是区域个数
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;      // 每个区域的起点 u 和终点 v
        // 把区域 [u,v] 里每一棵树的标记改为“被移走”
        for (int j = u; j <= v; j++) a[j] = 1;
    }
    int ans = 0;
    // 从 0 数到 l，统计还有多少棵树没被移走
    for (int i = 0; i <= l; i++) {
        if (a[i] == 0) ans++;
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

设马路的长度为 l，区域个数为 m。

• 时间：每个区域都要把 [u, v] 里的树标记一遍，最坏情况下每个区域几乎覆盖整条马路，所以时间复杂度是 O(m×l)。
• 空间：需要一个长度约为 l 的标记数组，空间复杂度是 O(l)。