本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-12 22:33:19

题目传送门

前言:

这道题是 CF1249D1 Too Many Segments (easy version) 的加强版，建议读者先去做一下此题，或是看一下它的题解，理解这两道题 贪心 的基本思路，以免看得一头雾水。

思路

额，本来想略过的，楼上 dalao 讲的很清楚了，但考虑到这是我洛谷上的第一篇题解，还是讲一讲吧。
题目要求我们删除一部分线段使得没有“坏点”的存在，那我们肯定要遍历一遍区间，找到哪个点是“坏点”后，才能进行操作。

当我们枚举到一个点时，如果这个点是“坏点”，那它肯定被多条线段所覆盖，枚举到这个点时，它前面的点一定都不是“坏点”（本来就不是“坏点”或在前面已经删掉一些线段使它不是“坏点”）。
那么当前覆盖这个点的线段的左端点对其毫无用处，无论删除多少条线段都不会改变这个点左面所有点是不是“坏点”，那我们可以关注右端点：

贪心地想，一条线段的右端点越“远”，那它就对更多的点有影响（贡献越大）。
所以，我们应该尽量删除右端点更靠右的线段。

细节及实现

实现

• 数据范围：$n \le 2\times10^5$ 并且 $l,r \le 2\times10^5$，这意味着遍历区间所有点就需要花费 $O(r_{max})$ 的时间复杂度，所以就无法再花费 $O(n)$ 的复杂度来枚举所有线段了。
• 考虑优化。我们可以用一个数据结构来存储覆盖到当前点的线段，考虑到要需要用排序维护右端点更靠右，最好用 priority_quque 或 set（我个人推荐用 set,因为 priority_quque 仅支持 priority_queue.top() 的删除）。
• 遍历到一个点时，可能会有多条线段以它为左端点，所以我们可以用二维的 vector 来存储线段的有关信息。

细节

• 题目要求输出线段的编号，所以我们的 set 和 vector 都是结构体，包括线段右端点和线段编号。
• 在遍历到一个新的点时，我们要把右端点小于当前点的线段删掉（容易想到这样的点已经“过期”了，对后续操作无用）。
• 我们在删除线段时仅保证右端点尽量大，不保证它的编号是升序的，所以要对 $ans$ 数组进行排序（以编号为关键字）。
• 感谢 STL 库 set 中有一个不常用的功能：set.rbegin() 指 set.end() 的前一个位置，在本题中就是右端点最大点所在的位置。
• set.begin()，set.rbegin() 等返回的都是元素所在的位置，使用时应加上符号“*”。

AC code

应该有部分读者最喜欢看这个，所以把它安排在最后

#include<bits\/stdc++.h>
#include<vector>
#include<set>
using namespace std;
#define int long long
#define re register
#define F(j,i,n)  for(re int i = j;i <= n;i++)
const int N = 2e5 + 50,M = 1e3 + 50;
inline void read(int &x){
	re int f = 1;x = 0;
	re char s = getchar();
	while(s < '0' || s > '9'){
		if(s == '-') f = -1;
		s = getchar();
	}while(s >= '0' && s <= '9')
		x = x * 10 + s - '0',s = getchar();
	x *= f;
}

int n,k;
int tot;\/\/被删除线段的数量 
struct node{
	int r,id;
	\/\/r记录区间的右端点
	\/\/id记录当前区间的编号
}ans[N];\/\/被删除线段的编号 
inline bool operator < (node a,node b){
	if(a.r == b.r) return a.id < b.id;
	return a.r < b.r;
	\/\/以右端点为关键字
}
inline bool cmp(node a,node b){
	return a.id < b.id;
	\/\/以编号为关键字升序排序
}
vector <node> a[N];
\/\/a[l]记录以l为左端点的线段的相关信息 
set <node> st;
\/\/set记录覆盖到当前点的线段 

signed main(){
	
	read(n),read(k);
	int l,r;
	node tmp;
	F(1,i,n){
		read(l),read(r);
		tmp.r = r,tmp.id = i;
		a[l].push_back(tmp);
	}
	
	F(1,i,200000){
		while(st.size() && (*st.begin()).r < i){\/\/区间的右端点小于当前点，说明这个区间已"过期"
			st.erase(*st.begin());
		}\/\/删除"过期"的区间
		
		for(int j = 0;j < a[i].size();j ++){
			st.insert(a[i][j]);
		}\/\/把以当前遍历到的点为左端点的区间插入至set
		
		while(st.size() > k){\/\/如果这个点是坏点
			ans[++ tot] = *st.rbegin();\/\/记录要被删除的区间
			st.erase(*st.rbegin());\/\/删除区间
		}
	}
	printf("%lld\n",tot);
	sort(ans + 1,ans + tot + 1,cmp);
	F(1,i,tot) printf("%lld ",ans[i].id);
	
	return 0;
}

最后的最后

本蒟蒻第五次申请题解，希望管理大大高抬贵手，把审核通过了吧~
第一次被打回：2024-06-13 10:08
第二次被打回：2024-07-05 14:18
第三次被打回：2024-07-08 15:47
第四次被打回：2024-07-10 22:21