校门外的树(解)

吐槽：第一次写题解，这玩意用着想吐是怎么回事？
但是，庆祝第一篇题解诞生了！噜噜噜……

题目： 长为l的路上种满了树，树从0开始到l，两树间隔一米，即0，1，2……，l都有一棵树；现在需要一些区域建地铁，区域用起止点表示（包含端点）。任一起止点都是整数，区域可能重合，求还剩多少树。

输入： 第一行输入两个整数 , ( , )代表马路长度和区域数目。
此后 行，第 行输入两个整数 和 ( )。

输出： 还剩多少树

1. 第一种方法是离散化的方法，把区间端点化，将一段区域的两端储存起来（结构体，pair等），并以左端点排序，将多个小区域转化成一个大区域，使得剩余区域没有重合的部分，最后只需简单的加和。
2. 第二种方法是前缀和的思路。将每次对整个区域的便历转化成对两端点的处理（即：q[x] ++, q[y] --, 其中 x 为左端点， y 为右端点），此时只要该点值仍为0（即：未发生变化）就表示该点有树，最后遍历得到结果。但数据量过大无法存储， pass!
3. 前缀和优化： 在普通前缀和中， 我们储存了整个数组，但每次操作只对两端点进行操作，造成了大量空间的浪费；因此，我们为啥不使用一种更简单的方式，即只对两端点进行存储，此时定义一个结构体，对每个区域的左右端点的位置及其属性进行存储（pos, num），并对位置进行遍历，当该位置的num为1，并且此时的总和为1（即：此处到前面那个区域位置间有树）就记录下来，最终得到结果。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

long long ans;
struct node{
    int pos, num;
}a[2*N];

bool cmp(node x, node y){
    if (x.pos == y.pos) return x.num < y.num;
    return x.pos < y.pos;
}

int main()
{
    int l, n;
    cin >> l >> n;
    for (int i = 1; i <= n; i ++)
    {
        int x, y;
        cin >> x >> y;
        a[i].pos = x;
        a[i].num = 1;
        
        a[i + n].pos = y + 1;
        a[i + n].num = -1;
    }
    
    sort(a + 1, a + 2*n + 1, cmp);
    
    int cnt = 0, p = 0;
    for (int i = 1; i <= 2*n; i ++)
    {
        p += a[i].num;
        if (p == 1 && a[i].num == 1) cnt += a[i].pos - a[i - 1].pos;
    }
    cnt += l - a[2*n].pos + 1;
    
    cout << cnt << endl;
    
    return 0;
}