本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-18 11:26:57

题目传送门

前言:

前置芝士

做完的可以去做 CF1249D1 Too Many Segments (hard version)，它是本题的加强版，我在本题中思路的实现和代码均是参考它的数据范围的。

思路

题目要求我们删除一部分线段使得没有“坏点”的存在，那我们肯定要遍历一遍区间，找到哪个点是“坏点”后，才能进行操作。

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

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

细节及实现

实现

• 数据范围：$n \le 200$ 并且 $l,r\le 200$，我们遍历区间所有点只需要花费 $O(r_{max})$ 的时间复杂度，所以就可以再花费 $O(n)$ 的复杂度来枚举所有线段了。
  但对于加强版，有 $n \le 2\cdot10^5$ 且 $l,r\le 2\cdot10^5$，明显上述做法的时间会爆掉。

• 考虑优化。我们可以用一个数据结构来存储覆盖到当前点的线段，考虑到要需要用排序维护右端点更靠右，最好用 priority_queue 或 set（我个人推荐用 set,因为 priority_queue 仅支持 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;
}

最后

如果有代码、思路问题，错别字问题及其他问题欢迎私聊