Steven_Meng's Blog

传送门

考虑把所有线段按照长度排序，在排好序的序列上面跑尺取法，设尺取法维护的区间为$[pl,pr]$，一直移动右端点$pr$，直到现在有一个点在区间$[pl,pr]$代表的线段上面出现$>=m$次，停止移动右端点，开始移动左端点，直到没有点在区间$[pl,pr]$代表的线段上面出现$>=m$次，在这个过程中统计答案即可。

具体实现时，先把线段离散化，再搞一棵支持区间加，区间查询最大值的线段树即可。

注意：数组开大一点，更新答案时不能用离散化后的$l,r$。

#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<3)+(x<<1)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
namespace SegmentTree{
    struct node{
        int l,r;
        int val,tag;
    }tree[MAXN<<2];
    #define lc i<<1
    #define rc i<<1|1
    inline void pushup(int i){
        tree[i].val=max(tree[lc].val,tree[rc].val);
    }
    inline void Change(int i,int val){
        tree[i].tag+=val;
        tree[i].val+=val;
    }
    inline void pushdown(int i){
        if (tree[i].tag){
            Change(lc,tree[i].tag);
            Change(rc,tree[i].tag);
            tree[i].tag=0;
        }
    }
    void Build(int i,int l,int r){
        tree[i].l=l,tree[i].r=r;
        tree[i].val=tree[i].tag=0;
        if (l==r) return ;
        int mid=(l+r)>>1;
        Build(lc,l,mid);
        Build(rc,mid+1,r);
    }
    void Update(int i,int L,int R,int val){
        if (L<=tree[i].l&&tree[i].r<=R){
            Change(i,val);
            return ;
        }
        int mid=(tree[i].l+tree[i].r)>>1;
        pushdown(i);
        if (L<=mid) Update(lc,L,R,val);
        if (mid<R) Update(rc,L,R,val);
        pushup(i);
    }
    int Query(int i,int L,int R){
        if (L<=tree[i].l&&tree[i].r<=R){
            return tree[i].val;
        }
        int mid=(tree[i].l+tree[i].r)>>1,ans=-0x7fffffff;
        pushdown(i);
        if (L<=mid) ans=max(ans,Query(lc,L,R));
        if (mid<R) ans=max(ans,Query(rc,L,R));
        return ans;
    }
}
using namespace SegmentTree;
struct Segment{
    int l,r,len;
}p[MAXN];
inline bool operator < (Segment A,Segment B){
    return A.len<B.len;
}
int n,m;
int num[MAXN<<1],cnt,maxn;
inline void discrete(){
    sort(num+1,num+1+cnt);
    cnt=unique(num+1,num+1+cnt)-num-1;
    for (register int i=1;i<=n;++i){
        p[i].l=lower_bound(num+1,num+1+cnt,p[i].l)-num;
        p[i].r=lower_bound(num+1,num+1+cnt,p[i].r)-num;
        maxn=max(maxn,p[i].l);
        maxn=max(maxn,p[i].r);
    }
}
int main(){
    n=read(),m=read();
    for (register int i=1;i<=n;++i){
        int l=read(),r=read();
        p[i]=Segment{l,r,r-l};
        num[++cnt]=l,num[++cnt]=r;
    }
    discrete();
    sort(p+1,p+1+n);
    int ans=0x7fffffff;
    int pl=1,pr=0;
    Build(1,1,maxn);
    while (true){
        while (pr<=n){
            if (Query(1,1,maxn)>=m) break;
            pr++;
            Update(1,p[pr].l,p[pr].r,1);
        }
        if (Query(1,1,maxn)<m) break;
        while (pl<=pr){
            if (Query(1,1,maxn)<m) break;
            ans=min(ans,p[pr].len-p[pl].len);
            Update(1,p[pl].l,p[pl].r,-1);
            pl++;
        }
    }
    printf("%d\n",ans==0x7fffffff?-1:ans);
}