寒假每日一题day7 AcWing 422. 校门外的树（三种写法的区间合并）线段树写法待补

422. 校门外的树

题意：

给你一个数轴，在轴上都有点，原本每个点上都有树。
现在给你m个区间，在这些区间覆盖的点上没有树。
问：
最后剩下多少树。

---

思路1（直接暴力）

复杂度：O（nm） ，m为区间长度
题目的数据小可以直接暴力。

每读入一个区间暴力标记即可。

AC1

# include <bits/stdc++.h>

using namespace std;

const int N = 1e4+10;
int x[N];

int main(){
    int l, m;
    cin>>l>>m;
    for(int i = 1; i <= m; i ++ ){
        int a, b;
        cin>>a>>b;
        for(int j = a; j <= b; j ++ )x[j] = 1;
    }
    int ans  = 0;
    for(int i = 0; i <= l; i ++ )ans+=(!x[i]);
    cout<<ans<<endl;
    return 0;
}

---

思路2(差分)

复杂度：O（m） ，m为区间长度
差分。

AC2

# include <bits/stdc++.h>

using namespace std;

const int N = 1e4+10;
int a[N];
int main(){
    int n, m;
    cin>>n>>m;
    while(m--){
        int l, r;
        cin>>l>>r;
        a[l]++; a[r+1]--;
    }
    int res = !a[0];
    for(int i = 1; i <= n; i ++ )res += !(a[i]+=a[i-1]);
    cout<<res<<endl;
    return 0;
}

---

思路3（对区间进行排序）

复杂度：O（nlogn） ，n为区间个数

AC3

/*
皮卡丘冲鸭！
へ　　　　　／|
　　/＼7　　　 ∠＿/
　 /　│　　 ／　／
　│　Z ＿,＜　／　　 /`ヽ
　│　　　　　ヽ　　 /　　〉
　 Y　　　　　`　 /　　/
　ｲ●　､　●　　⊂⊃〈　　/
　()　 へ　　　　|　＼〈
　　>ｰ ､_　 ィ　 │ ／／
　 / へ　　 /　ﾉ＜| ＼＼
　 ヽ_ﾉ　　(_／　 │／／
　　7　　　　　　　|／
　　＞―r￣￣`ｰ―＿
*/
#include <iostream>
#include <bits/stdc++.h>
#define For(i,x,y) for(int i=(x); i<=(y); i++)
#define fori(i,x,y) for(int i=(x); i<(y); i++)
#define rep(i,y,x) for(int i=(y); i>=(x); i--)
#define mst(x,a) memset(x,a,sizeof(x))
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>pa;
typedef pair<ll,ll>pai;
const int N = 1E5+10;
pa seg[N];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m;
    cin>>n>>m;
    For(i,1,m)cin>>seg[i].fi>>seg[i].se;
    sort(seg+1,seg+m);
    int res = n+1;
    int st = seg[1].fi, ed = seg[1].se; 
    For(i,2,m){
        if(seg[i].fi<=ed)ed=max(ed,seg[i].se);
        else {
            res -= ed-st+1;
            st = seg[i].fi;
            ed = seg[i].se;
        }
    }
    res -= ed-st+1;
    cout<<res<<endl;
    return 0;
}

---

思路4 线段树or树状数组。

大佬的题解

---

思路5 珂朵莉树

大佬的题解传送门