校门外的树（差分思想和区间合并思想）

两种思想

1.区间合并思想

using namespace std;
int m, times;
struct ty{
    int x,y;
}a[1005];
bool cmp(ty a, ty b){
    if(a.x < b.x) return 1;
    return 0;
}


int main(){
    scanf("%d%d", &m, &times);
    for(int i = 1; i <= times; i++){
        scanf("%d%d", &a[i].x, &a[i].y);
    }
    sort(a + 1, a + times + 1, cmp);
    int l = a[1].x, r = a[1].y;
    int ans = m + 1;
//     printf("%d ", ans);
    for(int i = 2; i <= times; i++){
        if(a[i].x < r)
            r = max(r, a[i].y);
        else{
            ans -= (r - l + 1);
            l = a[i].x, r = a[i].y;
        }
//         printf("%d %d %d ", l, r, ans);
    }
    ans -= (r - l + 1);
    cout << ans;
    return 0;
}

说明：不断进行区间合并，实现区间只计算一次，不断遍历实现。

2.差分数组思想

using namespace std;
int m, times;
int cnt;
struct ty{
    int num,tag;
}a[1005];
bool cmp(ty a, ty b){
    if(a.num < b.num) return 1;
    return 0;
}


int main(){
    scanf("%d%d", &m, &times);
    for(int i = 1; i <= times; i++){
        scanf("%d%d", &a[i].num, &a[i + times].num);
        a[i].tag = 1;
        a[i + times].tag = -1;
    }
    sort(a + 1, a + 2 * times + 1, cmp);
    int flag = 0;
    int ans = a[1].num;
//     printf("%d ", ans);
    for(int i = 1; i <= times * 2 - 1; i++){
        flag += a[i].tag;
        if(flag == 0){
            ans += (a[i + 1].num - a[i].num - 1);
        }
//         printf("%d %d %d ", l, r, ans);
    }
    ans += (m - a[2 * times].num);
    cout << ans;
    return 0;
}

说明：差分数组的思想，在区间的端点实现区间的整个实现的改变，同时根据题目中区间数目少而区间范围大，则选择通过抽取端点，进而实现整个区间的更新