本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-02-20 19:28:32

CF1249D2 Too Many Segments (hard version) 题解

原题链接

题目描述

给定 $n$ 个区间以及一个数字 $k$，每对 $l,r$ 覆盖的区间会 $+1$，求至少要删除多少个区间才能使得每个位置的值都不超过 $k$，输出删除的最小个数 $m$ 及删除的方案。

做法

看到数据范围，$n$ 是 $2\times10^5$ 的级别，我们需要一个 $O(n \log n)$ 的做法。

首先我们处理区间加减，这一点可以使用差分数组实现，我们在需要修改开头 $l$ 位置 $+1$，在结尾 $r + 1$ 位置 $-1$。

然后我们来考虑怎么样删除可以使得删除数量最少。由于删除的先后没有影响，所以我们可以从左往右依次检验每个点，所以要先把区间按照左端点从小到大排序。

我们考虑，对于一个点，我们考虑删除包含它的区间，我们可以每次将所有左端点小于等于当前点位置的区间都存起来。

那么我们怎么删除一些区间可以使得结果更优呢？

不难想到，对于所有位于当前点 $i$ 前面的点都已经被处理完了，所以我们删除的区间要尽可能地对 $i$ 后面的点产生贡献。

所以删除的方法就显而易见了，我们每次在所有的存储下来的对 $i$ 有贡献的区间里面，优先选择右端点 $r$ 靠右的区间，这样可以使得这个区间尽可能对后面较多的点产生贡献。

于是我们可以使用优先队列来存储这些区间，在优先队列中我们按照右端点从大到小排序。每次取出堆顶区间，由于当前区间对 $i$ 前面的所有点都没有了贡献，所以我们可以直接在差分数组上把 $i$ 处 $-1$，并把 $r$ 处 $+1$，直到当前节点值 $\le k$，再继续往后处理。

在处理同时将每次选出的堆顶区间记录下来，让 $cnt + 1$，最后输出即可。

AC Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int maxn = 2e5 + 10;
struct note{
	int l,r,id;
}se[maxn];

bool cmp(note a,note b)
{
	return a.l < b.l;
}

struct ccmp{
	inline int operator () (const note &a,const note &b) const
	{
		return a.r < b.r;
	}
};

int d[maxn];
priority_queue<note,vector<note>,ccmp> q;
vector<int> ans;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	int n,k;
	cin >> n >> k;
	for(int i = 1;i <= n;i++)
	{
		cin >> se[i].l >> se[i].r;
		se[i].id = i;
		d[se[i].l]++;
		d[se[i].r + 1]--;
	}
	sort(se + 1,se + n + 1,cmp);
	int now = 1;
	int cnt = 0;
	for(int i = 1;i <= 2e5;i++)
	{
		d[i] += d[i - 1];
		while(now <= n && se[now].l <= i)
		{
			q.push(se[now]);
			now++;
		}
		while(d[i] > k && !q.empty())
		{
			note p = q.top();
			q.pop();
			d[i]--;
			d[p.r + 1]++;
			cnt++;
			ans.push_back(p.id);
		}
	}
	cout << cnt << endl;
	for(int i = 0;i < cnt;i++) 
	{
		cout << ans[i] << " ";
	}
	return 0;
}

如果想要看弱化（数据范围较小）版本，请移步 CF1249D1 Too Many Segments (easy version)。

感谢阅读，希望对你有所帮助。