NC16649 校门外的树

思路

对于长度为L的马路，一开始共有L+1棵树

如果直接声明长度为L+1的数组再根据输入的区间一个一个遍历把树移走的话，一个区间有n个数就要执行n次操作，太过复杂，耗费时间比较长，数据小还可以操作，数据大的话就不行了，所以这题可以考虑差分和前缀和

有L+1棵树，为了方便操作，在数组最前面和最后面再加两个数，所以这里声明L+3长度的数组。
数组的每个元素代表数轴上这个点比上一个点多了多少棵树，数组第一个元素为1，即一开始所有点上都有树。
只需要把区间左端点处的树自减，右端点后一个点处的树自增即可。后面输出的时候从数组的第一个元素一直遍历到倒数第二个元素，用num计算当前点树的个数，如果num为正数就让sum+1，否则sum保持不变

代码

#include<iostream>

using namespace std;

int main() {
    int L, M;
    cin >> L >> M;
    //数组的每个元素表示该点比上一个点多几颗树
    //从数组第二个元素开始为数轴上下标为0的点
    int trees[L + 3];
    //对数组初始化
    trees[0] = 1;
    for (int i = 1; i < L + 3; ++i) {
        trees[i] = 0;
    }
    for (int i = 0; i < M; ++i) {
        int temp;
        cin >> temp;
        //从这里开始每个点砍掉一棵树
        trees[temp + 1]--;
        cin >> temp;
        trees[temp + 2]++;
    }
    int num = 1;
    int sum = 0;
    for (int i = 1; i < L + 2; ++i) {
        num += trees[i];
        sum += num > 0 ? 1 : 0;
    }
    cout << sum;
}