题意分析

题目要求计算道路上剩余的树木数量。初始时，道路从$0$米到$L$米每隔$1$米种一棵树，共 $L+1$ 棵。随后给定多个不重叠的占用区间，每个区间内的树木（包括端点）会被移除，需计算剩余树木总数。

解题思路

1. 初始树数计算：长度为 $L$ 的道路，树木位置为 $0, 1, 2, \dots, L$，共 $L+1$ 棵。
2. 区间树木移除：每个占用区间 $[\text{Start}, \text{End}]$ 包含 $\text{End} - \text{Start} + 1$ 棵树（端点包含在内）。由于区间不重叠，直接累加所有区间的树木数量并从总数中扣除即可。
3. 高效计算：无需遍历每个位置，通过数学方法直接计算每个区间的长度，时间复杂度为 $O(M)$，适用于 $L$ 极大的情况（如 $2 \times 10^9$）。

代码解释

#include <cstdio>
#include <cstdlib>
#include <cstring>

int main(void) {
    unsigned int trees; // 初始树木数（道路长度L）
    int M;              // 占用区间数量
    unsigned int start, end; // 区间起点和终点

    while (scanf("%u%d", &trees, &M), trees != 0 || M != 0) {
        // 初始树木数为L+1（0到L共L+1个点）
        trees += 1; 
        for (int i = 0; i < M; i++) {
            scanf("%u%u", &start, &end);
            // 区间[start, end]包含end - start + 1棵树，从总数中扣除
            trees -= (end - start + 1); 
        }
        printf("%u\n", trees);
    }
    return 0;
}

注意事项

1. 初始树数计算：
   • 道路长度为 $L$ 时，树木数量为 $L+1$（包含$0$米和$L$米处的树），代码中通过 trees += 1 正确处理。
2. 区间长度计算：
   • 区间 $[\text{Start}, \text{End}]$ 的树木数量为 $\text{End} - \text{Start} + 1$（两端点均包含），直接相减后加$1$即可。
3. 输入处理：
   • 使用 unsigned int 存储长度和坐标，避免负数问题。
   • 循环终止条件为 $trees == 0$ 且 $M == 0$，通过逗号表达式确保输入正确解析。
4. 数据范围：
   • 题目中 $L$ 可达 $2 \times 10^9$，但 $M \leq 5000$，算法效率极高，无需担心性能问题。

复杂度分析

• 时间复杂度：$O(M)$，每个测试用例遍历 $M$ 个区间，进行常数时间计算。
• 空间复杂度：$O(1)$，仅存储输入参数和临时变量。