CF1249D2 Too Many Segments (hard version)

给你条线段每条线有起始点和终止点线段会覆盖一个直线上的到的所有点问你取消多少条线段后可以使每一个点都不被大于的数量的线段覆盖。## 前置知识考虑对于第个点之前的所有点都满足了要求如果不满足要求要去掉一些线段那么肯定是要选右端点最大的因为左边已经不管了去掉之后对右边的影响越大越好这时候时间复杂度是的。#includebits/stdc.h using namespace std; const int N2e25; struct node{ int l,r,id; }; node a[N]; int n,k,tot,s[N],sum[N]; bool cmp(node x,node y){ if(x.ry.r) return x.ly.l; return x.ry.r; } int main(){ scanf(%d%d,n,k); for(int i1;in;i){ scanf(%d%d,a[i].l,a[i].r); a[i].idi; } sort(a1,an1,cmp); for(int i1;in;i){ for(int ja[i].l;ja[i].r;j){ sum[j]; if(sum[j]k){ s[tot]a[i].id; break; } } } printf(%d\n,tot); for(int i1;itot;i){ printf(%d ,s[i]); } return ~(-1); }做法对于的情况我们可以用优先队列优化然后模拟也是一样的。#includebits/stdc.h using namespace std; #define int long long const int N2e55; struct node{ int l,r,id; }; node a[N]; bool cmp(node x,node y){ return x.ly.l; } struct cmp_r { bool operator()(const node a, const node b) const { return a.r b.r; } }; int n,k,now1,res0,d[N]; priority_queuenode,vectornode,cmp_r q; vectorint ans; signed main(){ scanf(%lld%lld,n,k); for(int i1;in;i){ scanf(%lld%lld,a[i].l,a[i].r); a[i].idi; d[a[i].l]; d[a[i].r1]--; } sort(a1,an1,cmp); for(int i1;iN-5;i){ d[i]d[i-1]; while(nowna[now].li){ q.push(a[now]); now; } while(d[i]k!q.empty()){ node pq.top(); q.pop(); d[i]--; d[p.r1]; res; ans.push_back(p.id); } } printf(%lld\n,res); for(int i0;ires;i) printf(%lld ,ans[i]); return 0;