[NOIP 2005 普及组] 校门外的树

知识点

数组、区间标记、计数

解题思路

道路位置0到L初始都有树。对每个施工区间[l,r]逐点标记为移除，最后统计未被移除的位置。

正确性说明

每个位置被标记当且仅当它属于至少一个施工区间。重复标记不影响结果，最终未标记的位置与保留的树一一对应。

易错点

道路两端0和L都各有一棵树，所以初始总数为L+1；施工区间含左右端点；重叠区间不能重复扣树。

复杂度

最坏时间O(ML+L)，空间O(L)，符合本题范围。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    int L,M;cin>>L>>M;vector<bool> removed(L+1,false);
    while(M--){int l,r;cin>>l>>r;for(int i=l;i<=r;++i)removed[i]=true;}
    int ans=0;for(bool x:removed) if(!x)++ans;
    cout<<ans<<'\n';
}