不得不说，这也许会是一道长期在我的博客里作为“HARD”难度存在的题
这道题能很好的考验选手的思考能力，但本蒟蒻最后还是听了省队爷讲了之后才会。。。（默默面壁）
题目里，说对于每一个点，是用当前选出的M个里面，最长长度减去最短长度作为价值。也就是说：选择长度介于最长与最短之间的边，是对答案没有影响的。（本蒟蒻并没有想到这一点。。。）
所以由于这一点，我们可以先对于边的长度排序。
那么题目中提到的M，是“选中多余或等于M条边”，从这里就可以看出，我们只需要选定一个头和一个尾就好，由此可以看出，这个子问题完全可以用尺取法处理。
以尺取法不停更新最优解就好啦。
那么怎么处理M捏，其实很简单，用离散化加线段树就可以解决关于“M个点“的子问题。
直接甩题目&代码
Description
在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
Input
第一行包含两个正整数 n,m用空格隔开，意义如上文所述。保证 1≤m≤n
接下来 n行，每行表示一个区间，包含用空格隔开的两个整数 li 和 ri 为该区间的左右端点。
N<=500000,M<=200000,0≤li≤ri≤10^9
Output
只有一行，包含一个正整数，即最小花费。
Sample Input
6 3
3 5
1 2
3 4
2 2
1 5
1 4
3 5
1 2
3 4
2 2
1 5
1 4
Sample Output
2
/**************************************************************
Problem: 4653
User: PencilWang
Language: C++
Result: Accepted
Time:12896 ms
Memory:87320 kb
****************************************************************/ #include<stdio.h>
#include<string.h>
#include<algorithm>
#include<set>
using namespace std;
struct shit1{int L,R,lon;}e[];
struct shit2{int L,R,lazy,num;}s[];
int fucker[];
int ans,n,m,k;
bool cmp(shit1 a,shit1 b)
{
return a.lon<b.lon;
}
void push_down(int p)
{
int L=p<<,R=p<<|;
s[L].num+=s[p].lazy;
s[L].lazy+=s[p].lazy;
s[R].lazy+=s[p].lazy;
s[R].num+=s[p].lazy;
s[p].lazy=;
return ;
}
void push_up(int p)
{
s[p].num=max(s[p<<].num,s[p<<|].num);
return ;
}
void build(int p,int L,int R)
{
s[p].L=L,s[p].R=R;
if(L==R)return ;
int mid=(L+R)>>;
build(p<<,L,mid);
build(p<<|,mid+,R);
return ;
}
void add(int a,int b,int p,int num)
{
if(a<=s[p].L&&s[p].R<=b)
{
s[p].num+=num;
s[p].lazy+=num;
return ;
}
push_down(p);
int mid=(s[p].L+s[p].R)>>;
if(a<=mid)add(a,b,p<<,num);
if(b>mid)add(a,b,p<<|,num);
push_up(p);
return ;
}
set<int>sb;
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d%d",&e[i].L,&e[i].R);
sb.insert(e[i].L);sb.insert(e[i].R);
e[i].lon=e[i].R-e[i].L+;
}
for(set<int>::iterator p=sb.begin();p!=sb.end();++p)
fucker[++m]=*p;
build(,,m);
sort(e+,e+n+,cmp);
for(int i=;i<=n;i++)
{
e[i].L=lower_bound(fucker+,fucker+m+,e[i].L)-fucker;
e[i].R=lower_bound(fucker+,fucker+m+,e[i].R)-fucker;
}
int L=,R=;
int Lz=e[].lon,Rz=e[].lon;
while(e[R].lon==Rz)
add(e[R].L,e[R].R,,),R++;
R--;
ans=0x3f3f3f3f;
while(L<=R&&R<=n)
{
if(s[].num>=k)
{
ans=min(ans,Rz-Lz);
while(e[L].lon==Lz)
add(e[L].L,e[L].R,,-),L++;
Lz=e[L].lon;
}
else
{
Rz=e[++R].lon;
while(e[R].lon==Rz&&R<=n)
add(e[R].L,e[R].R,,),R++;
if(R==n+)break;
R--;
}
}
if(ans==0x3f3f3f3f)ans=-;
printf("%d",ans);
return ;
}