做题记录22.3.31 洛谷P2250

由于CSDN新增了字数限制，即日起本人开始转战博客园

题目链接

这题我原本的想法是：按先x后y的升序排序，随后对于任意一个i，查找和i+1相交的部分，并在这部分从右往左种树。最后进行检查，把不满足条件的地点种上树即可。但这种方法好像难以实现，因为情况比较多，比如完全包含、部分相交、完全不相交等。

其实可以这样思考：既然要种得尽可能少，那么完全可以在每一个区间都从右向左。但应当按照先y后x升序排序。否则会导致 一个区间完全包含在另一个区间的情况出现错误。

sort(a+1,a+h+1,[&](Tree a,Tree b) {
	return (r=a[i].l; j--) {
		if(vis[j])	cnt[i]++;
	}
	//在尾部种树
	for(int j=a[i].r; j>=a[i].l&&cnt[i]