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
Sample Output

2

题解

这题一开始看错题了QAQ以为是选的线段的总和最小。。
然后想了很久。。
后来发现看错了。。
那么这种题一般都是排序加乱搞吧。。最多就是有个二分答案之类的。。
这题考虑排序，肯定是按值来拍啊显而易见
然后你维护两个指针L和R
表示我们现在选择的线段。。
怎么判有没有解呢？用个线段树维护一下就好了啊。。要是最大值有比m大的就是有解的，然后每加入一条线段就区间加，删除同理 log维护，O(1)查询
然后我们让R从左往右扫
对于一个R值，L值与他越近肯定差值越小的。。
于是每次R移动完就尽量移动L，直到不可行为止。。
并且R要是单调向右，L肯定是单调向右的
因为要是L,R是一个合法的答案，L,R+1肯定是不会作为答案的。。
于是这题就做完了
CODE：

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=500005*2;
const int MAX=1<<30;
int a[N],cnt=0;//离散化? 
struct qq
{int l,r;int c;//他的值 
}s[N];
int n,m;
int get (int x)
{int l=1,r=cnt;while (l<=r){int mid=(l+r)>>1;if (a[mid]==x) return mid;else if (a[mid]>x) r=mid-1;else l=mid+1;}
}
void LSA ()
{sort(a+1,a+1+cnt);int ccnt=cnt;cnt=1;for (int u=2;u<=ccnt;u++)if (a[u]!=a[cnt])a[++cnt]=a[u];
/* for (int u=1;u<=cnt;u++)printf("%d ",a[u]);printf("\n");*/for (int u=1;u<=n;u++){s[u].l=get(s[u].l);s[u].r=get(s[u].r);}
/* printf("\n");for (int u=1;u<=n;u++)printf("%d %d %d\n",s[u].l,s[u].r,s[u].c);*/
}
bool cmp (qq a,qq b){
   return a.c<b.c;}
struct qr
{int l,r;int s1,s2;int c;//出现了多少次int lazy;
}tr[N*2];int num=0;
int mymax (int x,int y){
   return x>y?x:y;}
int mymin (int x,int y){
   return x<y?x:y;}
void bt (int l,int r)
{int a=++num;tr[a].l=l;tr[a].r=r;tr[a].c=0;tr[a].lazy=0;if (l==r)   return ;int mid=(l+r)>>1;tr[a].s1=num+1;bt(l,mid);tr[a].s2=num+1;bt(mid+1,r);
}
void update (int x)
{int s1=tr[x].s1,s2=tr[x].s2;int lazy=tr[x].lazy;tr[x].lazy=0;tr[s1].lazy+=lazy;tr[s1].c+=lazy;tr[s2].lazy+=lazy;tr[s2].c+=lazy;
}
void change (int now,int l,int r,int c)
{if (tr[now].l==l&&tr[now].r==r){tr[now].c+=c;tr[now].lazy+=c;return ;}update(now);int mid=(tr[now].l+tr[now].r)>>1;int s1=tr[now].s1,s2=tr[now].s2;if (r<=mid) change(s1,l,r,c);else if (l>mid) change(s2,l,r,c);else change(s1,l,mid,c),change(s2,mid+1,r,c);tr[now].c=mymax(tr[s1].c,tr[s2].c);
}
int main()
{scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)   {scanf("%d%d",&s[u].l,&s[u].r);s[u].c=s[u].r-s[u].l;a[++cnt]=s[u].l;a[++cnt]=s[u].r;}LSA();sort(s+1,s+1+n,cmp);
// for (int u=1;u<=n;u++) printf("%d %d %d\n",s[u].l,s[u].r,s[u].c);bt(1,cnt);int L=1,R=1;change(1,s[1].l,s[1].r,1);int ans=MAX;while (R<=n){while (L<=R){if (tr[1].c>=m){ans=mymin(ans,s[R].c-s[L].c);change(1,s[L].l,s[L].r,-1);L++;}else break;}/* printf("YES:%d %d\n",L,R);for (int u=1;u<=num;u++)printf("%d %d %d\n",tr[u].l,tr[u].r,tr[u].c);system("pause");*/R++;if (R<=n) change(1,s[R].l,s[R].r,1);}if (ans==MAX) printf("-1");else printf("%d\n",ans);return 0;
}