题解 | #剩下的树#

不能使用集合转化的方法，因为时间复杂度超出：

1. 遍历所有区间，将序号记录到新的数组中
2. 使用std::set方法将新数组转化为集合，这样重复的树的序号会被清除
3. 使用size()方法统计集合的大小，就是移除树木的数量

下面计算此方法的时间复杂度：

1. 因为set方法基于红黑树实现，时间复杂度为logn，设要转化的含有重复序号的移除的树木的数组长度为n，则每查找一次重复的数字就需要时间logn，所以时间复杂度为nlogn，又假设最坏情况，每个区间的长度都为L，则n=L，所以时间复杂度为LlogL；
2. 遍历每个区间，假设最坏情况，每个区间长度都是L，则需要遍历ML次，时间复杂度为ML；
3. 综上，由于LlogL>ML，所以整体时间复杂度为LlogL

所以时间差在了集合的转化上。

为了不使用集合的转化，在每次得到区间后就处理树木的数量，使用bool数组，只需对所有区间遍历一次即可，时间复杂度为ML：

#include <iostream>
#include <vector>

// 使用bool数组计算，true代表有一棵树，false代表没有树
// 时间复杂度：ML

int main() {
	int L, M;
	std::cin >> L >> M;
	// 创建一个布尔数组，初始时所有位置都有一棵树
	std::vector<bool> trees(L + 1, true);
	// 接收输入，每输入一次坐标就计算🌳
	for (int i = 0; i < M; i++) {
		int start, end;
		std::cin >> start >> end;
		// 将要移走树的区间内的所有元素设为false
		for (int j = start; j <= end; j++) {
			trees[j] = false;
		}
	}
	// 计算剩下的树的数量
	int count = 0;
	for (bool tree : trees) {
		if (tree) {
			count++;
		}
	}
	std::cout << count << std::endl;

	return 0;
}