---
title: "校门外的树"
created: 2025-11-28
tags:
  - 算法
---

# 校门外的树

## 题目 [校门外的树](https://www.acwing.com/problem/content/424/)

![[image-4b75221d.png]]

## 思路分析

是模版的变形

也可以作为 农田灌溉
[[2-Learning/02-算法/03-刷题理模型/区间合并相关问题/管道|管道]] 无线网络 这三题的一个引入

可以用标记的方式 遍历标记查看数目 也可以用区间合并

<https://www.acwing.com/solution/content/193960/>

这篇还给出了线段树、树状数组等方式的解答 等以后学到了回过头来看一下

要注意几个点

0~400 401~500

这一段是可以合并的 与模版有些不同

所以要把不合并的条件修改为 ed+1<road.first

其次注意一个计数问题

1~2 是2-1+1棵树

所以每个区间应该是 r-l+1棵

其他没什么了

## 代码实现

原模板stl 19ms

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

typedef pair<int,int> PII;

vector<PII> roads;

int L,M;

int main()

{

    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>L>>M;

    for(int i=0;i<M;i++){

        int l,r;

        cin>>l>>r;

        roads.push_back({l,r});

    }

    sort(roads.begin(),roads.end());

    int st=-100,ed=-100;

    int res=0;

    for(auto road:roads){

        if(ed+1<road.first){

            if(ed!=-100)

                res+=ed-st+1;

            st=road.first,ed=road.second;

        }

        else if(ed<road.second)

            ed=road.second;

    }

    if(ed!=-100)

        res+=ed-st+1;

    cout<<(L+1)-res<<endl;

    return 0;

}
```

优化模板 14ms

```cpp
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

const int N=100010;
typedef pair<int,int> PII;
PII roads[N];
int cnt=0;
int L,M;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>L>>M;
    for(int i=0;i<M;i++){
        int l,r;cin>>l>>r;
        roads[cnt++]={l,r};
    }
    sort(roads,roads+M);

    int st=-100,ed=-100;
    int res=0;
    for(int i=0;i<M;i++){
        if(ed+1<roads[i].first){
            if(ed!=-100)    res+=ed-st+1;
            st=roads[i].first,ed=roads[i].second;
        }
        ed=max(roads[i].second,ed);
    }
    if(ed!=-100)    res+=ed-st+1;
    cout<<(L+1)-res<<endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[2-Learning/02-算法/03-刷题理模型/区间合并相关问题/救生员|救生员]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/区间合并相关问题/管道|管道]]