来自FallDream的博客，未经允许，请勿转载，谢谢
在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 −1。
n<=500000 m<=200000
考虑离散之后按照长度排序，从小到大加入线段，用线段树维护一下被覆盖最多次的点覆盖了多少次。每当这个次数大等于m，就让没用的线段全部出队，并且统计答案。
复杂度nlogn
#include<iostream> #include<cstdio> #include<algorithm> #define MN 500000 #define INF 2000000000 using namespace std; inline int read() { int x = 0; char ch = getchar(); while(ch < '0' || ch > '9') ch = getchar(); while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x; } struct Node{int l,r,val,x;}T[MN*8+5]; struct seg{int l,r,len;}s[MN+5]; int cnt=0,n,m,p[MN*2+5],tot=1,ans=INF; bool cmp(seg x,seg y){return x.len<y.len;} void build(int x,int l,int r) { if((T[x].l=l)==(T[x].r=r)) return; int mid=l+r>>1; build(x<<1,l,mid); build(x<<1|1,mid+1,r); } inline void mark(int x,int ad){T[x].x+=ad;T[x].val+=ad;} inline void pushdown(int x){mark(x<<1,T[x].val);mark(x<<1|1,T[x].val);T[x].val=0;} void Modify(int x,int l,int r,int ad) { if(T[x].l==l&&T[x].r==r) {mark(x,ad);return;} if(T[x].val) pushdown(x); int mid=T[x].l+T[x].r>>1; if(r<=mid) Modify(x<<1,l,r,ad); else if(l>mid) Modify(x<<1|1,l,r,ad); else Modify(x<<1,l,mid,ad),Modify(x<<1|1,mid+1,r,ad); T[x].x=max(T[x<<1].x,T[x<<1|1].x); } int main() { n=read();m=read(); for(int i=1;i<=n;++i) p[++cnt]=s[i].l=read(),p[++cnt]=s[i].r=read(),s[i].len=s[i].r-s[i].l; sort(s+1,s+n+1,cmp);sort(p+1,p+cnt+1); for(int i=2;i<=cnt;++i) if(p[i]!=p[i-1]) p[++tot]=p[i]; for(int i=1;i<=n;++i) s[i].l=lower_bound(p+1,p+tot+1,s[i].l)-p, s[i].r=lower_bound(p+1,p+tot+1,s[i].r)-p; build(1,1,tot); for(int i=1,j=0;i<=n;++i) { Modify(1,s[i].l,s[i].r,1); if(T[1].x>=m) { for(;T[1].x==m;)++j,Modify(1,s[j].l,s[j].r,-1); ans=min(ans,s[i].len-s[j].len); } } printf("%d ",ans==INF?-1:ans); return 0; }