题解 | #剩下的树#

提供一种O(n+m)的思路。

利用差分数组可以实现O(1)进行一次区间操作，而计算具体某个元素的时间复杂度为O(n)（一次性计算所有元素的值时间复杂度为O(n)）。因为本题先进行一系列区间操作，最后再询问一次所有元素的值，因此十分适合用差分数组求解。

对于本题，可将原数组初值设置为0，表示树还在，而后续砍树操作看做区间减1操作，最后再计算修改后的数组的值，当值小于0，说明被砍了，反之还在，统计结果即可。

差分数组

定义

diff[i]=a[i]-a[i-1],i>=1（a为原数组，diff为差分数组）

diff[0]=a[0]

显然，a[i]=diff[0]+...+diff[i]

区间操作

对[l,r]进行加x操作，转化为：

diff[l]+=x

diff[r+1]-=x

//
// Created by Zed on 2024/1/27.
//

#include <iostream>
const int MAXN=1e4+10;
using namespace std;
int diff[MAXN];//差分数组

int main() {
    int L,M;
    while(cin>>L>>M){
        int l,r;
        for (int i = 0; i < L+2; ++i) {
            diff[i]=0;//默认初始值为0
        }
        for (int i = 0; i < M; ++i) {
            cin>>l>>r;
            diff[l]--;//对[l,r]区间进行减1操作
            diff[r+1]++;
        }
        int cur=0;
        int ans=L+1;
        for (int i = 0; i < L+1; ++i) {
            cur+=diff[i];//累加计算第i个元素的值
            if(cur<0){//若值小于0,说明编号i的树被砍了
                ans--;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}