雨巨无敌

方法一：差分

对m个区域进行差分数组delta [ i ]维护

• 本质上是 如果有一个区间砍树 相应的原数组就+1。
• 在差分数组上表现为 区间左端点 +1 区间右端点的下一个 -1
• 维护好这个数组后 求差分数组的前缀和 得到原数组a [ i ]即可 判断是否等于0
• 如果等于0 代表没有被砍树

using namespace std;
/**
采用前缀和与差分的思想
首先维护数组delta[i] 初值都为0
当有某一个区间要砍树时 对应的点就加一  等价为对区间端点进行差分处理
最后求差分数组的前缀和得到原数组
如果原数组值a[i] == 0 那么说明树没砍
计数器cnt++
最后输出cnt
*/
int delta[10010];
int cnt = 0;
int main()
{
    int l,m;
    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;
    for(int i = 0; i <= l; i++)
    {
        a += delta[i];
        if(a == 0)
            cnt++;
    }
    cout<<cnt;
}

方法二：划分区域

• 用结构体zone去表示数轴上的区域，并按照左端点x的大小进行依次排序。
• 将有交集的区域合并在一起，如果遇到第一个与前一个没有交集的区域，就变成新的left与right，然后在数轴上减去前一段合并区域的长度

using namespace std;
struct zone
{
    int x,y;
}a[110]; //用结构体表示区域
bool comp(zone a, zone b)
{
    return a.x < b.x;
}
int main()
{
    int l,m;
    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); //由于是结构体 因此要自己定义comp 从小到大排序
    
    int left = a[1].x;
    int right = a[1].y;
    int cnt = l + 1; //树的总数
    for(int i = 2; i <= m; i++)
    {
        if(a[i].x <= right) //这里可以加等号
        {
            right = max(right,a[i].y);
        }
        else
        {
            cnt -= (right - left + 1);
            left = a[i].x;
            right = a[i].y;
        }
    }
    cnt -= (right - left + 1);
    cout<<cnt;
}

方法三 离散化，即区间合并+差分

实际上 在差分的思想中，求前缀和很多时候是无用功，对于一个区间的中间部分，不断的加0还是本身，所以我们思考，用一个结构体，只记录区间端点的num：-1，1，以及他们的位置pos：x，y。当前缀和a==1并且delta[i].num==1时，说明当前i是挖掉树的区间的开始，用delta[i].pos - delta[i-1].pos就可以得到树的个数，加在cnt中即可。最后一段要单独加

using namespace std;
//离散化的思想 即区间合并与前缀和差分的结合体
struct zone
{
    int pos,num;
}delta[500];
bool comp(zone a, zone b)
{
    return a.pos < b.pos;
}
int main()
{
    int l,m;
    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 a = 0;
    int cnt = 0;
    for(int i = 1; i <= 2*m; i++)
    {
        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;
}