贪心、数据结构、线段树

线段题经典套路，考虑贪心选择死的最快（$r_i$ 最小）的僵尸攻击。需要一种快速判断当前僵尸能不能选的方式，这里使用支持区间加和区间 $\max$ 的线段树。

时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;
struct Segment{int l,r,w,m;}s[1'600'005];
struct Line{int l,r;}a[200'005];
int n,m,ans,cnt,p[400'005];
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r;
    if(l==r) return;
    build(u*2,l,(l+r)/2);
    build(u*2+1,(l+r)/2+1,r);
}
void mark(int u,int k){s[u].w+=k,s[u].m+=k;}
void pushdown(int u){mark(u*2,s[u].m),mark(u*2+1,s[u].m),s[u].m=0;}
void update(int u,int l,int r){
    if(s[u].l>r||s[u].r<l) return;
    if(s[u].l>=l&&s[u].r<=r) return mark(u,1);
    pushdown(u);
    update(u*2,l,r),update(u*2+1,l,r);
    s[u].w=max(s[u*2].w,s[u*2+1].w);
}
int query(int u,int l,int r){
    if(s[u].l>r||s[u].r<l) return 0;
    if(s[u].l>=l&&s[u].r<=r) return s[u].w;
    pushdown(u);
    return max(query(u*2,l,r),query(u*2+1,l,r));
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
    for(int i=1;i<=n;i++) p[++cnt]=a[i].l,p[++cnt]=a[i].r;
    sort(p+1,p+cnt+1),cnt=unique(p+1,p+cnt+1)-p-1;
    sort(a+1,a+n+1,[](auto x,auto y){return x.r<y.r;});
    build(1,1,cnt);
    for(int i=1;i<=n;i++){
        a[i].l=lower_bound(p+1,p+cnt+1,a[i].l)-p;
        a[i].r=lower_bound(p+1,p+cnt+1,a[i].r)-p;
        if(query(1,a[i].l,a[i].r-1)==m) ++ans;
        else update(1,a[i].l,a[i].r-1);
    }
    printf("%d\n",ans);
    return 0;
}