题解：P3602 Koishi Loves Segments

· · 题解

本来以为是 DP 什么的，结果看标签发现是贪心（可能是我太蒻了）。
首先将线段按左端点升序排序，兴奋的点也按坐标升序排序，方便处理。我们可以发现，这么排序后，在覆盖于点上的线段超过 x 条时，右端点更大的可能会覆盖较多的点，所以右端点更大的线段一定不优。
有注意到 \lvert l\rvert,\lvert r\rvert,\lvert p\rvert \le 10^7，需要离散化，这里因为线段端点可能重复，所以使用 multiset。

code：

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=4e5+5;
struct seg{//线段
    int l,r;
}a[N];
struct point{//兴奋点
    int p,x;
}b[M];
bool cmp1(seg a,seg b){//按照线段的左端点排序
    return a.l<b.l;
}
bool cmp2(point a,point b){//按坐标排序
    return a.p<b.p;
}
int n,m,ans;
multiset<int>s;//默认按升序排序
int main(){
    int n,m;
    cin>>n>>m;
    ans=n;
    for(int i=1;i<=n;i++){
        cin>>a[i].l>>a[i].r;
    }
    for(int i=1;i<=m;i++){
        cin>>b[i].p>>b[i].x;
    }
    sort(a+1,a+1+n,cmp1);
    sort(b+1,b+1+m,cmp2);
    int idx=1;//在a数组中的下标
    for(int i=1;i<=m;i++){//维护每一个兴奋点
        while(idx<=n&&a[idx].l<=b[i].p){//加入所有可能覆盖当前点的线段
            s.insert(a[idx++].r);
        }
        while(s.size()&&*s.begin()<b[i].p){//删去未覆盖当前点的线段
            s.erase(s.begin());
        }
        while(s.size()>b[i].x){//多于x个且右端点最大的一定不优，删除
            s.erase(--s.end()),ans--;
        }
    }
    cout<<ans;
    return 0;
}