NC16649 [NOIP2005]校门外的树

题目

题目描述

某校大门外长度为 \(L\) 的马路上有一排树，每两棵相邻的树之间的间隔都是 \(1\) 米。我们可以把马路看成一个数轴，马路的一端在数轴 \(0\) 的位置，另一端在 \(L\) 的位置；数轴上的每个整数点，即 \(0,1,2,\cdots,L\)都种有一棵树。

由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。

输入描述

第一行有两个整数：\(L\)（\(1 \leq L \leq 10000\)）和 \(M\)（\(1 \leq M \leq 100\)），\(L\) 代表马路的长度，\(M\) 代表区域的数目，\(L\) 和 \(M\) 之间用一个空格隔开。接下来的 \(M\) 行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。

输出描述

包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。

示例1

输入

500 3
150 300
100 200
470 471

输出

298

题解

数据范围一（原题范围）：$L \leq 10^4 $ ，$ M \leq 10^2$

思路

知识点：差分。

数组直接模拟整个区间，进行差分。

时间复杂度 \(O(L+M)\)

空间复杂度 \(O(L)\)

代码

#include 

using namespace std;

int vis[10007];///模拟整个区间

int main(){
    int L,M;
    cin>>L>>M;
    for(int i = 0;i>l>>r;
        vis[l]++;
        vis[r+1]--;///差分
    }
    int a = 0,ans = 0;
    for(int i = 0;i<=L;i++){
        a += vis[i];///前缀和
        if(!a) ans++;///加完之后是0，那说明此处无遮盖
    }
    cout<

#include 

using namespace std;

struct qj{
    int l,r;
}a[100007];

bool cmp(qj a,qj b){
    return a.l == b.l?a.r>L>>M;
    for(int i = 0;i>a[i].l>>a[i].r;
    }
    sort(a,a+M,cmp);///按左端点从小到大，再按右端点从小到大

    int cnt = 0;///记录合并区间长度
    int l = a[0].l,r = a[0].r;///记录初始合并区间
    for(int i = 1;i

#include 

using namespace std;

struct diff{
    int pos;
    int num;
}delta[100007];///记录特定端点代替整个区间，达到满足空间要求


bool cmp(diff a,diff b){
    return a.pos==b.pos?a.num>L>>M;
    for(int i = 0;i>x>>y;
        delta[i].pos = x;///记录左端点
        delta[i].num = 1;

        delta[i+M].pos = y+1;///记录右端点，因为差分所以y+1
        delta[i+M].num = -1;
    }
    sort(delta,delta+2*M,cmp);///根据左端点从小到大排序，先负再正
    int a = 0,cnt = 0;
    for(int i = 0;i<2*M;i++){
        a += delta[i].num;
        if(a == 1 && delta[i].num == 1){///此时pos是0区域的右端点+1位置,上一个pos即左端点位置
            cnt+=delta[i].pos - delta[i-1].pos;///相减即为区间长度
        }
    }
    if(!a) cnt+=L-delta[2*M-1].pos+1;
    cout<