题解 | #值周#

和 《校门外的树》 是一样的思路，但数据量要稍微大一些

#include <bits/stdc++.h>
using namespace std;

//和 校门外的树 一样
const int N = 1e8 + 5;
int l, m, s[N], a[N];

int main(){
    cin >> l >> m;
    while(m --){
        int x, y;
        cin >> x >> y;
        //构造差分序列
        a[x] ++, a[y + 1] --;
    }
    //求前缀和，值为0即有人
    int ans = (s[0] = a[0]) ? 0 : 1;
    for(int i = 1; i <= l; i ++){
        s[i] = s[i - 1] + a[i];
        if(!s[i]) ans ++;
    }

    cout << ans;
}