难度： 蓝

算法： 线段树，差分约束

一本通常规乱打标签。

差分约束时间复杂度 $O(n^2)$。显然无法通过，或者被卡 SPFA。

下面给出 $O(n\log^2n)$ 的线段树做法。这是我的除模板题以外第一次使用线段树，写的不好请见谅。

在下文中记区间个数为 $n$，所有区间中最大的右端点为 $m$。

对于每个点，$0$ 表示没种树，$1$ 表示种了。开始时，所有点均为 $0$。

考虑1.1例2的思想。将所有区间按照右端点从小到大排序，然后依次处理。对于区间 $i$，表示第 $l_i$ 至 $r_i$ 中至少有 $s_i$ 棵树。

显然这个区间内可能已经有一些树，故只需要种植不够的数量即可，如果不用种就跳过。为了使树被包含在更多的区间内，我们应该优先在右边种。使用二分求出最大的 $p\in [l_i,r_i]$，使得在 $[p,r_i]$ 种上树以后 $[l_i,r_i]$ 内的树的数量大于等于 $s_i$。然后将 $[p,r_i]$ 中所有数设为 $1$ 表示已经种过树。

区间的左右端点都可能是 $0$，于是将所有区间右移一位。最后统计有多少树即可。

使用线段树维护以上区间修改和区间查询操作，二分和线段树各有一个 log，时间复杂度 $O(n\log^2n)$，可以通过。

代码如下，由于本人线段树写的不熟练，请谨慎使用此代码。

#include<bits/stdc++.h>
using namespace std;
struct tr{
	int l,r,la,sum;
}x[500200];
struct nd{
	int a,b,c;
}d[50050];
bool cmp(nd fi,nd se){
	return fi.b<se.b;
}
void build(int le,int ri,int id){//建树 
	x[id].l=le,x[id].r=ri;
	if(le==ri) return ;
	build(le,(le+ri)/2,2*id);
	build((le+ri)/2+1,ri,2*id+1);
}
void turn(int le,int ri,int id){//将 le 至 ri 中所有数修改为 1 
	int nl=x[id].l,nr=x[id].r,mid=(nl+nr)/2;
	if(x[id].la==1) x[id*2].la=1,x[id*2+1].la=1;
	if(le<=nl&&nr<=ri){ 
		x[id].la=1;
		x[id].sum=nr-nl+1;
		return ;
	}	
	if(le<=mid) turn(le,ri,id*2);
	if(ri>mid) turn(le,ri,id*2+1);
	x[id].sum=x[2*id].sum+x[2*id+1].sum;
}
int que(int le,int ri,int id){//查询 le 至 ri 中所有数的和 
	int nl=x[id].l,nr=x[id].r,mid=(nl+nr)/2;
	if(x[id].la==1) x[id*2].la=1,x[id*2+1].la=1,x[id].sum=nr-nl+1;
	if(le<=nl&&nr<=ri) return x[id].sum;
	int ret=0;
	if(le<=mid) ret+=que(le,ri,id*2);
	if(ri>mid) ret+=que(le,ri,id*2+1);
	return ret;
}
int n,le,ri,mid,m;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>d[i].a>>d[i].b>>d[i].c;
		d[i].a++,d[i].b++;
		m=max(m,d[i].b);
	} 
	sort(d+1,d+n+1,cmp);
	build(1,m,1);
	for(int i=1;i<=n;i++){
		le=d[i].a,ri=d[i].b;
		if(d[i].c<=que(le,ri,1)) continue;
		while(le<ri){
			mid=(le+ri)/2;
			if(que(d[i].a,mid,1)+d[i].b-mid+1>d[i].c) le=mid+1;
			else ri=mid;
		}
		turn(le,d[i].b,1);
	}
	cout<<que(1,m,1);
	return 0;
}