题解 | #校门外的树#

代码1：

#include <bits/stdc++.h>
using namespace std;
//前缀和表示区域内树的数量

int l, m, s[10005], a[10005];

int main(){
    cin >> l >> m;
    for(int i = 0; i <= l; i ++)
        a[i] = 1, s[i] = i + 1;

    while(m --) {
        int x, y; cin >> x >> y;
        //区域内每个点都变为0
        for(int i = x; i <= y; i ++) a[i] = 0;
    }

    //求前缀和
    s[0] = a[0];
    for(int i = 1; i <= l; i ++)
        s[i] = s[i - 1] + a[i];

    cout << s[l];
}

非常不理解，求前缀和的部分也是从前到后遍历一遍，但是换成以下代码就会超时：

    int ans = 0;
    for(int i = 1; i <= l; i ++)
        if(a[i]) ans ++;
    cout << ans

只是用了个前缀和居然就能过。

代码2：

看了其他人的题解，使用了差分算法。我不是很熟悉，所以学习了以后自己写了一遍。

#include <bits/stdc++.h>
using namespace std;
//前缀和表示区域内树的数量

int l, m, s[10005], a[10005];

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

    while(m --) {
        int x, y; cin >> x >> y;
        //差分
        a[x] ++, a[y + 1] --;
    }

    //求前缀和 判断剩余数量

    s[0] = a[0];
    for(int i = 1; i <= l; i ++)
        s[i] = s[i - 1] + a[i];

    //s值为0即代表有树
    int ans = 0;
    for(int i = 0; i <= l; i ++)
        if(s[i] == 0) ans ++;

    cout << ans;

}