一道 naive 题当做普通扫描线想了 10min，还要继续努力！

把线段按长度升序排序，进行双指针扫描。

把坐标离散化，线段树维护指针间的线段在数轴上各处的出现次数，支持区间加、全局 max 查询。

右端点保持移动，直到出现单点为 $m$ 的部分，改为左端点右移至不存在。

在移动过程中统计答案。

解完。

Code

map/set 离散化在 uoj 被 hack 数据卡常了。

建议 sort/unique/lower_bound 离散化捏。

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
struct Seg
{
    uint len,tag,max;Seg*L,*R;
    Seg(uint n):len(n),tag(0),max(0),L(NULL),R(NULL){if(n>1)L=new Seg(n>>1),R=new Seg(n-(n>>1));}
    voi add(uint l,uint r,uint v)
    {
        if(l>=r)return;
        if(!l&&r==len){tag+=v,max+=v;return;}
        if(l<(len>>1))
            if(r<=(len>>1))L->add(l,r,v);
            else L->add(l,len>>1,v),R->add(0,r-(len>>1),v);
        else R->add(l-(len>>1),r-(len>>1),v);
        max=std::max(L->max,R->max)+tag;
    }
};
uint L[500005],R[500005];
std::pair<uint,std::pair<uint,uint> >P[500005];
uint A[1000005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint n,m;scanf("%u%u",&n,&m);
    for(uint i=0;i<n;i++)scanf("%u%u",L+i,R+i),A[i<<1]=L[i],A[i<<1|1]=R[i];
    std::sort(A,A+(n<<1));uint cnt=std::unique(A,A+(n<<1))-A;
    for(uint i=0;i<n;i++)P[i]={R[i]-L[i],{std::lower_bound(A,A+cnt,L[i])-A,std::lower_bound(A,A+cnt,R[i])-A+1}};
    std::sort(P,P+n);Seg S(cnt);
    uint ans=-1;
    for(uint r=0,l=0;;)
    {
        while(r<n&&S.max<m)S.add(P[r].second.first,P[r].second.second,1),r++;
        if(S.max<m)break;
        while(l<r&&S.max==m)_min(ans,P[r-1].first-P[l].first),S.add(P[l].second.first,P[l].second.second,-1),l++;
    }
    printf("%d\n",(int)ans);
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
#define maxn 500000
#define inf (1<<30)
#define read(x) scanf("%d",&x)
struct Pair
{
	int x,y;
	int sz;
	Pair(){}
	Pair(int xx,int yy) {x=xx,y=yy;}
	bool operator < (const Pair& oth) const
	{
		return sz<oth.sz;
	}
} a[maxn+5];
int n,m;
map<int,int> mp;
int cnt;
struct SGT
{
	#define mid (L+R)/2
	#define lson o*2
	#define rson o*2+1
	int c[maxn*10+5],lzy[maxn*10+5];
	int P,Q,sz;
	SGT(){}
	void Set(int L,int R) {P=L,Q=R;}
	void push_down(int o)
	{
		c[lson]+=lzy[o],c[rson]+=lzy[o];
		lzy[lson]+=lzy[o],lzy[rson]+=lzy[o];
		lzy[o]=0;
	}
	void push_up(int o)
	{
		c[o]=max(c[lson],c[rson]);
	}
	void Add(int o,int L,int R,int d)
	{
		if(L>Q||R<P) return ;
		if(L>=P&&R<=Q)
		{
			c[o]+=d,lzy[o]+=d;
			return ;
		}
		push_down(o);
		Add(lson,L,mid,d),Add(rson,mid+1,R,d);
		push_up(o);
	}
} sgt;
int main()
{
	read(n),read(m);
	for(int i=1;i<=n;i++)
	{
		read(a[i].x),read(a[i].y),a[i].sz=a[i].y-a[i].x;
		mp[a[i].x]=mp[a[i].y]=true;
	}
	for(map<int,int>::iterator it=mp.begin();it!=mp.end();++it)
	{
		mp[it->first]=++cnt;
	}
	for(int i=1;i<=n;i++)
	{
		a[i].x=mp[a[i].x],a[i].y=mp[a[i].y];
	}
	sort(a+1,a+n+1);
	int t=1,ans=inf;
	for(int i=1;i<=n;i++)
	{
		sgt.Set(a[i].x,a[i].y);
		sgt.Add(1,1,n*2,1);
		while(sgt.c[1]>=m)
		{
			ans=min(ans,a[i].sz-a[t].sz);
			sgt.Set(a[t].x,a[t].y);
			sgt.Add(1,1,n*2,-1);
			t++;
		}
	}
	
	printf("%d",ans==inf?-1:ans);
	
	return 0;
}