↓ 跳过正文
题解：AT_nikkei2019_final_d Deforestation

题解：AT_nikkei2019_final_d Deforestation

xyx404
作者
xyx404
Have a nice day.
目录

洛谷专栏链接。

题目：
#

在我写题解时题目翻译有错误，故此处放上简略的正确翻译。

有 $N$ 根竹子，编号从 $1$ 到 $N$。初始时，所有竹子的高度是 $0$，时间每过一秒，每根竹子的高度增加 $1$。

有 $M$ 个砍伐计划，第 $i$ 个计划在 $T_i$ 时，将砍掉编号在 $L_i$ 和 $R_i$ 之间的竹子。当竹子砍下时高度为 $x$ 时，会得到 $x$ 的竹子。被砍掉的竹子高度将变为 $0$，之后还会生长。

求可以得到多少竹子。

完整题目，点击此处。

思路：
#

因为每过一秒高度都会增加一，且砍后会继续生长，所以我们可以只计算第 $i$ 个竹子最后是在什么时候被砍掉的，这个时间就是这个竹子的高度。

实现，在输入后我们可以直接从最后开始向前遍历，因为题目满足输入的时间 $T_i$ 一定小于等于 $T_{i+1}$。

定义一个 set，类型为 int，名字叫 $se$，用来标记这个竹子有没有砍过。

用 lower_bound 函数查找在 $se$ 里第一个大于等于 $L_i$ 的值的位置，然后遍历编号在 $L_i$ 和 $R_i$ 之间的竹子，加上现在的时间也就是可以从竹子身上得到的竹子，并把这个竹子从 $se$ 里删除。

代码：
# 

#include<bits/stdc++.h>
using namespace std;
set<int>se;
int n,m;
int t[200005],l[200005],r[200005];
long long ans=0;
void solve(){
	for(int i=1;i<=n;i++)se.insert(i);// 记录有没有砍 
	for(int i=m;i>=1;i--){
		auto it=se.lower_bound(l[i]);// 二分查找第一个大于等于 l[i] 的值的位置
		while(it!=se.end()&&*it<=r[i]){
			ans+=t[i];
			se.erase(it++);
		}
	}
	cout<<ans<<"\n";
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>t[i]>>l[i]>>r[i];
	}
	solve();
	return 0;
}