笔记

思路一

一个长度为L，全部为0的数列。现在统计各个点被覆盖的次数，每个点被覆盖一次就加1，最后找数列里为0的点即可。 实现：利用差分数组维护区间加1的操作

#include<bits/stdc++.h>
using namespace std;
int l,m;
int delta[10010];
int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i<= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x > y) swap(x, y);
        delta[x]++;
        delta[y+1]--;
    }
    int a = 0, cnt = 0;
    for (int i = 0; i <= l; i++)
    {
        a += delta[i];
        if (a == 0) cnt++;
    }
    cout << cnt;
}

思路二

有交集的区间可以合并成一个大区间，汇总成几个互不相交的长区间。区间长度即为挖走的树的个数。

只需要把区间按左界排序，判断它的右界和下一个区间的左界的位置关系。右界取两个区间最大的那个

（特殊情况：第二个区间完全在第一个区间里面）

#include<bits/stdc++.h>
using namespace std;
int l,m;
struct ty
{
    int x, y;
}a[1000];

bool comp(ty a, ty b)
{
    if (a.x < b.x) return 1;
    return 0;
}

int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i<= m; i++)
    {
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    sort (a+1, a+1+m, comp);
    int cnt  = l+1;
    int l = a[1].x, r = a[1].y;
    for(int i = 2; i <= m; i++)
    {
        if (a[i].x < r)
        {
            r = max(r, a[i].y);
        }
        else{
            cnt -= (r-l+1);
            l = a[i].x, r = a[i].y;
        }
    }
    cnt -= (r-l+1);
    cout << cnt;
}

思路三

离散化

给端点值做标记，开始挖树的点标记值+1，结束的点-1

#include<bits/stdc++.h>
using namespace std;
int l,m;
struct ty
{
    int pos, num;
}delta[1000];

bool comp(ty a, ty b)
{
    if (a.pos == b.pos) return a.num < b.num;
    return a.pos < b.pos;
}

int main()
{
    scanf("%d%d", &l, &m);
    for (int i = 1; i<= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        delta[i].pos = x;
        delta[i].num = +1;
        
        delta[i+m].pos = y+1;
        delta[i+m].num = -1;
    }
    sort (delta+1, delta+1+2*m, comp);
    int cnt  = 0;
    int a = 0;
    for(int i = 1; i <= 2*m; i++)
    {
        a = a + delta[i].num;
        if (a == 1 && delta[i].num == 1)
            cnt += delta[i].pos - delta[i-1].pos;
    }
    cnt += l - delta[2*m].pos+1;
    cout << cnt;
}