题解

思路1

这个题 $1 \le l \le 10000$，快乐吧，暴力吧。 其实也算不上暴力，不过比起下面两种思路，时间复杂度 $O(lm)$ 倒是挺高了。 就是用一个标记数组 $a$，如果 $a_i == 1$，则 $i$ 处的树可怜的被挖掉了，否则 $i$ 处的树还在。这样思路一下就出来了，输入 $u$ 和 $v$，直接把中间全改成 $1$，重叠的话两次赋值都是 $1$，没有问题。最后用 $cnt$ 统计一下有多少 $a_i == 0$，输出就完了。

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, cnt = 0;
bool a[10005]; // 标记数组
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        for (int j = u; j <= v; j++) // 直接上
            a[j] = 1;
    }
    for (int i = 0; i <= l; i++) // 注意从0开始
    {
        if (a[i] == 0) // 统计
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

思路2

这个方法就是差分，啥是差分。差分可以看作前缀和的逆运算，啥是前缀和，就是有一个数组 $d$ 作为 $a$ 的差分数组，则： $a_i = a_{i - 1} + d_i$ 看明白了吗？没有。 那么我们让 $d$ 数组作为标记数组 $a$ 的差分数组，那么在清理 $u$ 到 $v$ 的树时，该如何改变这个数组呢？ 让我们先来模拟一下：

最开始啥也没有，一棵树都没拔掉，差分数组也都是 $0$。 当我们拔掉 $4$ 到 $6$ 的树时，我们修改完 $a$ 数组，发现 $d$ 数组是这样的：

在 $4$（$u$）的位置，差分数组为了让前面的 $0$ 变成 $1$，所以差分数组也是 $1$，而后面 $7$（$v + 1$）的位置，为了让 $1$ 回归 $0$，所以这里差分是 $-1$。 那如果后来又有 $3$ 到 $4$ 重叠了怎么办：

如果我们直接去加，$4$ 会变成 $2$，但是由于 $0$ 是还在，别的都拔了，这样理解也是拔掉了。 这是差分数组会变为：

我们算算发现差分数组依然合法。如果是 $0$ 到 $2$ 呢？

我们发现 $3$ 这里 $+1$ 和 $-1$ 抵消了，变成了 $0$，可是依然成立。 而且我们发现，每次修改差分数组，时间复杂度只有 $O(1)$ 我们最后还原出 $a$，统计 $a_i = 0$，时间复杂度也只是 $O(l)$，总时间复杂度 $O(m + l)$，小了不少。 差分方法也总结出来了：

d[u]++;
d[v + 1]--;

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, s = 0, cnt = 0;
int d[10005];
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        // 差分
        d[u]++;
        d[v + 1]--;
    }
    for (int i = 0; i <= l; i++)
    {
        s = s + d[i]; // 还原，这里可以节省为一个变量s
        if (s == 0) cnt++; // 统计
    }
    printf("%d\n", cnt);
    return 0;
}

思路2的升级

这里我们发现，有时差分数组里会有大片的 $0$ 空白，我们可以通过离散化，只记录不为 $0$ 的差分的位置与大小。 这个方法比较复杂，我们看看就可以。

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, s, cnt = 0;
struct node
{
    int pos;
    int num;
} d[10005]; // 差分数组
bool cmp(node a, node b) //按照先后顺序排序
{
    return a.pos < b.pos;
} 
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        // 记录差分
        d[i].num++;
        d[i].pos = u;
        d[i + m].num--;
        d[i + m].pos = v + 1;
    }
    sort(d + 1, d + 2 * m + 1, cmp); //按照先后顺序排序
    for (int i = 1; i <= 2 * m; i++)
    {
        s += d[i].num;
        if (s == 1 && d[i].num == 1) //a从0到1，说明前一段a全为0，即有树
            cnt += d[i].pos - d[i - 1].pos; // 计算这一段0
    }
    cnt += l - d[2 * m].pos + 1; // 计算最后一段0
    printf("%d\n", cnt);
    return 0;
}

这个最坏情况下，每次只能统计一个，不过时间复杂度也很不错，大概在 $O(m)$ 左右。 这里还是比较推荐法2，因为这个性价比不高（在这道题），复杂度不是很高，想的话不用多想，直接法1，大一点法2就足够了，这个没有优化多少，但是码量加了不少，容易写错，CSP建议法2。

$AC$ $Code$ $1$

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, cnt = 0;
bool t[10005];
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        for (int j = u; j <= v; j++)
            t[j] = 1;
    }
    for (int i = 0; i <= l; i++)
    {
        if (t[i] == 0)
            cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

$AC$ $Code$ $2$

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, s = 0, cnt = 0;
int d[10005];
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        d[u]++;
        d[v + 1]--;
    }
    for (int i = 0; i <= l; i++)
    {
        s = s + d[i];
        if (s == 0) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

$AC$ $Code$ $2+$

#include <bits/stdc++.h>
using namespace std;
int l, m, u, v, s, cnt = 0;
struct node
{
    int pos;
    int num;
} d[10005];
bool cmp(node a, node b)
{
    return a.pos < b.pos;
} 
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &u, &v);
        d[i].num++;
        d[i].pos = u;
        d[i + m].num--;
        d[i + m].pos = v + 1;
    }
    sort(d + 1, d + 2 * m + 1, cmp);
    for (int i = 1; i <= 2 * m; i++)
    {
        s += d[i].num;
        if (s == 1 && d[i].num == 1)
            cnt += d[i].pos - d[i - 1].pos;
    }
    cnt += l - d[2 * m].pos + 1;
    printf("%d\n", cnt);
    return 0;
}

主要思路就是打标记。

#include <bits/stdc++.h>
using namespace std;
int s, m, l, r, ans;
bool a[10005];//定义一个标记数组。
int main()
{
	cin >> s >> m;
	for (int i = 0; i <= m; i ++)
	{
		cin >> l >> r;
		for (int j = l; j <= r; j ++)
		{
			a[j] = 1;//把区间内所以地方打标记。
		}
	}
	for (int i = 0; i <= s; i ++)//遍历
	{
		if (a[i] != 1)  ans ++;//判断是否打标记并累加没打过标记的地方
	}
	cout << ans;
}

放心，已AC。

给个好评吧

#include<bits/stdc++.h>
using namespace std;
int t[100002],l,m,u,v,i,all;
int main()
{
    scanf("%d%d",&l,&m);
    while(i<m)
    {
        scanf("%d%d",&u,&v);
        int j=u;
        while(j<=v)
        {
            t[j]=1;
            j++;
        }
        i++;
    }
    i=0;
    while(i<=l)
    {
        if(t[i]==0)all++;
        i++;
    }
    printf("%d",all);
    return 0;
}

灰常简单 #include <bits/stdc++.h> using namespace std; int l, m, u, v, s = 0, cnt = 0; int d[10005]; int main() { scanf("%d%d", &l, &m); for (int i = 1; i <= m; i++) { scanf("%d%d", &u, &v); // 差分 d[u]++; d[v + 1]--; } for (int i = 0; i <= l; i++) { s = s + d[i]; // 还原，这里可以节省为一个变量s if (s == 0) cnt++; // 统计 } printf("%d\n", cnt); return 0; }

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,u,v,a[10005],sum=0;
    cin >> n >> m;
    memset(a,-1,sizeof(a));
    sum=n+1;
    for(int i=1;i<=m;i++)
    {
        cin >> u >> v;
        for(int j=u;j<=v;j++)
        {
            if(a[j]==-1)
            {
                sum--;
            }
            a[j]=0;
        }
    }
    cout << sum;
}