题解：CF1249D2 Too Many Segments (hard version)

Handezheng · 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