思路

按右端点满足最低种树数，补在最右空位可共享后续区间；与单点命中区间题不同，标准程序使用树状数组和前驱优化。

参考程序（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<int>p,bit;int f(int x){int y=x;while(p[y]!=y)y=p[y];while(p[x]!=x){int z=p[x];p[x]=y;x=z;}return y;}void add(int x){for(;x<(int)bit.size();x+=x&-x)bit[x]++;}int sum(int x){int a=0;for(;x;x-=x&-x)a+=bit[x];return a;}int main(){int n,m;cin>>n>>m;vector<tuple<int,int,int>>a;while(m--){int b,e,t;cin>>b>>e>>t;a.push_back({e,b,t});}sort(a.begin(),a.end());p.resize(n+1);iota(p.begin(),p.end(),0);bit.resize(n+1);int ans=0;for(auto z:a){int e=get<0>(z),b=get<1>(z),need=get<2>(z)-sum(e)+sum(b-1);while(need-->0){int x=f(e);add(x);p[x]=f(x-1);ans++;}}cout<<ans<<'\n';}