离散化+线段树

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std; typedef long long LL; #define INF 0x7fffffff#define N 5000010 int n,m; struct data{ int l,r,k; }a[N]; bool operator < (data x,data y){ return x.k
           
            '9' || ch<'0') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f;} inline void pushup(int now){ sum[now]=max(sum[now<<1],sum[now<<1|1]);} inline void pushdown(int now){ if (add[now]) { sum[now<<1]+=add[now]; sum[now<<1|1]+=add[now]; add[now<<1]+=add[now]; add[now<<1|1]+=add[now]; add[now]=0; }} inline void update(int nowl,int nowr,int now,int l,int r,int d){ if (nowl>=l && nowr<=r) { sum[now]+=d; add[now]+=d; return ; } pushdown(now); int mid=nowl+nowr>>1; if (l<=mid) update(nowl,mid,now<<1,l,r,d); if (r>mid) update(mid+1,nowr,now<<1|1,l,r,d); pushup(now);} inline int get(int x){ int l=1,r=cnt,mid; while (l
            
             >1; if (b[mid]>=x) r=mid; else l=mid+1; } return l;} int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { scanf("%d%d",&a[i].l,&a[i].r); a[i].k=a[i].r-a[i].l+1; b[++cnt]=a[i].l; b[++cnt]=a[i].r; } sort(a+1,a+n+1); sort(b+1,b+cnt+1); for (int i=1;i<=n;i++) a[i].l=get(a[i].l),a[i].r=get(a[i].r); for (int i=1,j=0;j<=n;) { if (sum[1]>m) { update(1,cnt,1,a[i].l,a[i].r,-1); i++; } else if (sum[1]