算法1

(模拟,数组遍历) $O(ML)$

定义一个长度为 $L + 1$ 的布尔数组，表示每棵树的状态。

• true 表示已经被移走；
• false 表示未被移走；

对于每次移动树木的操作 $[L_i, R_i]$，直接循环一遍，将布尔数组中从 $L_i$，到 $R_i$ 这段赋值为true。

最后统计值为 false 的数量即可。

时间复杂度分析

对于每次移动树木的操作，最坏情况下区间长度是 $O(L)$，因此计算量是 $O(L)$，一共有 $M$ 次操作，因此总时间复杂度是 $O(ML) = 100 \times 10000 = 10^6$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010;

int n, m;
bool st[N];

int main()
{
    scanf("%d%d", &m, &n);
    while (n -- )
    {
        int l, r;
        scanf("%d%d", &l, &r);
        for (int i = l; i <= r; i ++ ) st[i] = true;
    }

    int res = 0;
    for (int i = 0; i <= m; i ++ )
        if (!st[i])
            res ++ ;

    printf("%d\n", res);

    return 0;
}

算法2

(区间合并) $O(MlogM)$

先求出所有移动树木的操作的区间的并集，那么马路上剩余部分即为最终剩下树木的部分。

求所有区间的并集可以使用区间合并算法，可以参考 AcWing 803. 区间合并。

时间复杂度分析

区间合并算法的时间复杂度是 $O(MlogM)$，其中 $M$ 是区间数量。

C++ 代码

#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 110;

int n, m;
PII seg[N];

int main()
{
    cin >> m >> n;

    for (int i = 0; i < n; i ++ ) cin >> seg[i].first >> seg[i].second;

    sort(seg, seg + n);

    int res = m + 1;
    int st = seg[0].first, ed = seg[0].second;
    for (int i = 1; i < n; i ++ )
        if (seg[i].first <= ed) ed = max(seg[i].second, ed);
        else
        {
            res -= ed - st + 1;
            st = seg[i].first, ed = seg[i].second;
        }

    res -= ed - st + 1;

    cout << res << endl;

    return 0;
}