题目链接:https://ac.nowcoder.com/acm/contest/6013/H
题目大意:
图片说明
题目大意:给你n个线段。给你一个区间1-1e6.让你覆盖这些区间,要求区间上没有一个点被覆盖>k次,问最少有多少线段用不上,就是:n-最多可以用多少线段。

分析:我们知道如果k=1.是一个典型的贪心。按右端点排序从小到大选择。贪心的选择就可以了。
如果k!=1.其实是一样的就是k次贪心。把之前选择的线段去掉再重复这个贪心选择过程k次。当然模拟k次肯定是不行的。我们考虑用一个数据结构来维护这个区间覆盖次数。支持区间修改,区间查询。-线段树。这道题就写完了。

当然用另外一种维护方法可以直接用set维护(set保存线段右端点)。思路如下:按线段左端点排序。遍历当前端点。
1.如果当前set的最小值<a[i].l,就删除,一直到*set.begin()>a[i].l,因为这些删除的线段一定不会和i和i后面的线段起冲突。
2.如果set.size()<k直接把第a[i].r加入。ans++。
3.set.size()==k。说明前面的选择导致a[i].l有k条线段覆盖。如果之前的这k条线段的右端点最大值>a[i].r。那么用第i条线段去更换这条线段一定更优。假设这条线段是pos。因为比pos在前面加入set那么pos.l<=a[i].l,并且pos.r>a[i].r。用a[i].r去替换能给后面的线段创造更多机会。

还有一个问题假如pos:[1, 10] i:[5, 7]。用i去替换pos会不会导致[1, 4]这段区间有新的可行覆盖线段,没有计算入贡献。我们假设之前有[1, 4]没有加入set。说明在1点的时候size()==k。那么一定导致[1, 4]去替换[1, 10]。所以替换的时候不会增加贡献,只是给后面的线段创造机会。

//线段树
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int mx[N<<2],lazy[N<<2],n,k,res,up;
struct node{int l,r;}t[N];
#define mid (l+r>>1)
inline void push_down(int p){
    mx[p<<1]+=lazy[p],mx[p<<1|1]+=lazy[p];
    lazy[p<<1]+=lazy[p],lazy[p<<1|1]+=lazy[p];
    lazy[p]=0;
}
void change(int p,int l,int r,int ql,int qr,int v){
    if(l==ql&&r==qr){mx[p]+=v,lazy[p]+=v; return ;}
    push_down(p);
    if(qr<=mid)  change(p<<1,l,mid,ql,qr,v);
    else if(ql>mid)  change(p<<1|1,mid+1,r,ql,qr,v);
    else change(p<<1,l,mid,ql,mid,v),change(p<<1|1,mid+1,r,mid+1,qr,v);
    mx[p]=max(mx[p<<1],mx[p<<1|1]);
}
int ask(int p,int l,int r,int ql,int qr){
    if(l==ql&&r==qr)    return mx[p];
    push_down(p);
    if(qr<=mid)  return ask(p<<1,l,mid,ql,qr);
    else if(ql>mid)  return ask(p<<1|1,mid+1,r,ql,qr);
    else return max(ask(p<<1,l,mid,ql,mid),ask(p<<1|1,mid+1,r,mid+1,qr));
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)    scanf("%d %d",&t[i].l,&t[i].r),up=max(up,t[i].r);
    sort(t+1,t+1+n,[](node a,node b){
        return a.r<b.r;
    });
    for(int i=1;i<=n;i++)    if(ask(1,1,up,t[i].l,t[i].r)<k){
        res++;  change(1,1,up,t[i].l,t[i].r,1);
    }
    cout<<n-res;
    return 0;
}

//set
#include<bits/stdc++.h>
using namespace std;

struct node{
    int l, r;
}a[1000005];
multiset<int> st;
int main(){
    int n, k, ans=0; scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++){
        scanf("%d%d", &a[i].l, &a[i].r);
    }
    sort(a+1, a+1+n, [](node &a, node &b){
        return a.l<b.l;
    });
    for(int i=1; i<=n; i++){
        while(!st.empty()&&(*st.begin())<a[i].l){
            st.erase(st.begin());
        }
        if(st.size()<k){
            st.insert(a[i].r);
            ans++;
        }
        else{
            if(*(--st.end())>a[i].r){
                st.erase(--st.end());
                st.insert(a[i].r);
            }
        }
    }
    printf("%d\n", n-ans);

    return 0;
}