题意：
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
只有一行，包含一个正整数，即最小花费。
题解 ：
首先将线段离散化不会对答案有影响
如果考虑右移重复m次的点会发现答案的最小值会很难维护
所以考虑将线段按长度排序后依次加入
这样做的话，可以看到如果有一个合法方案最长为i，最短为j，那么长度小于j的线段我们完全可以无视掉
因为随着我们加入线段的增长，解会更劣。
所以我们可以维护一个指针p代表我们关心的线段中最短的那条，同时相交用线段树维护
每加入一条线段，我们在线段树上将这条线段的区间加1，如果整棵线段树最大值等于m了，就尝试从p开始向后删除线段，直到线段树最大值小于m，我们就已经找到一组解了
代码 ：
#include<bits/stdc++.h> #define INF 0x3f3f3f3f using namespace std; inline int _min(int a,int b) {return a<b?a:b;} inline int _max(int a,int b) {return a>b?a:b;} #define MAXN 500005 int n,m; struct line{ int l,r,len; bool operator < (const line &a) const { return len<a.len; } }x[MAXN]; int w[MAXN*2],hash[MAXN*2],top; int BS(int v) { int l=1,r=top,mid,ret=1; while(l<=r) { mid=l+r>>1; if(hash[mid]<=v) l=mid+1,ret=mid; else r=mid-1; } return ret; } namespace SegmentTree{ struct node{ int add,mx; }x[MAXN*8]; void Modify(int num,int l,int r,int nl,int nr,int v) { if(l==nl&&r==nr) {x[num].add+=v;x[num].mx+=v;return;} int mid=l+r>>1; if(nl>mid) Modify(num<<1|1,mid+1,r,nl,nr,v); else if(nr<=mid) Modify(num<<1,l,mid,nl,nr,v); else {Modify(num<<1,l,mid,nl,mid,v);Modify(num<<1|1,mid+1,r,mid+1,nr,v);} x[num].mx=_max(x[num<<1].mx,x[num<<1|1].mx)+x[num].add; } int QMax() {return x[1].mx;} } #define ST SegmentTree int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d%d",&x[i].l,&x[i].r); x[i].len=x[i].r-x[i].l;w[i]=x[i].l;w[i+n]=x[i].r; } sort(x+1,x+1+n);sort(w+1,w+2*n+1); hash[++top]=w[1]; for(int i=2;i<=n<<1;i++) { if(w[i]==w[i-1]) continue; hash[++top]=w[i]; } for(int i=1;i<=n;i++) { x[i].l=BS(x[i].l);x[i].r=BS(x[i].r); } int p=1,ans=INF; for(int i=1;i<=n;i++) { ST::Modify(1,1,top,x[i].l,x[i].r,1); if(ST::QMax()>=m) { while(ST::QMax()>=m) {ST::Modify(1,1,top,x[p].l,x[p].r,-1);p++;} ans=_min(ans,x[i].len-x[p-1].len); } } if(ans==INF) puts("-1"); else printf("%d ",ans); return 0; }