CF1249D2 题解

· · 题解

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)。

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