值周

思路

不同于校门外的树 ,这一题要用到差分数组优化(这一部分内容可以看acwing基础模板)
可以先尝试构造差分数组, 然后再还原回来
考虑到可能多次取重叠的区间, 最后还原的时候, 需要找到原来那些不被破坏的点,进行统计

ac代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int main()
{
    int L, M;
    cin >> L >> M;
    vector<int> a(L + 1, 0); // [0 ,L]
    a[0] = 1;                // s0 也是 1
    while (M--)
    {
        int l, r;
        cin >> l >> r;
        a[l] += 1, a[r + 1] -= 1;
    }
    long long cnt = 0, ans = 0;
    for (int i = 0; i <= L; i++)
    {
        cnt += a[i];
        if (cnt == 1)
            ans++; // 原来数组上应该都是 1 统计这部分人即可
    }
    cout << ans;
    return 0;
}