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

分析：

这道题是从abclzr的课件中扒出来的

学长的课件上说的很简单：带删除的区间覆盖问题，标记永久化

等我看到了真正的题面就蒙了

冷静。。你可以的。。。

我们可以把一个个区间看做是覆盖在数轴上的，

每次某个点的覆盖次数==m之后，就统计一下答案

然后删除一个覆盖区间，继续进行添加

但是我们要选择哪一个删除呢

最小的？ 万一之后覆盖上了一个更短的，那么就不如删掉最长的优了

最长的？ 万一之后覆盖上了一个更长的，那么就不如删掉最短的优了

中间的？ 万一。。肯定不行啊

如果我们能让ta们按照一定的长度顺序（比如说从小到大）添加就好了

等等，这一点我们好像可以做到

我们先把所有的区间按照长度排序

之后再添加（线段树维护的区间操作）

显然长度相近的的区间出现m覆盖的情况最优

如果出现区间m重叠的情况，就计算一下答案，然后删除最短的那个区间

继续添加

这样算法的雏形就浮出水面了

看了一下数据范围，丧心病狂

看来还要离散化一下

虽然语言描述好像挺复杂，但是真正转化成程序就要简单得多

因为我们每次添加的一定是排序后一个区间内的线段

（长度相近的一定是在一个区间内）

我们枚举区间左端点l，暴力向右扩展右端点

在线段树的每个节点中记录一个sum信息

表示这个节点维护的数轴中最多被覆盖了几次

每次看一下t[1].sum，如果==m就记录一下答案

tip

我们在枚举左端点向右移的过程中，右端点是单调不减的

因为其他情况已经被前面的状态计算过了

一开始我认为：我们每次看的是t[1]的信息，

任何一个小区间的信息都可以统计到t[1]上，所以我们不用下放标记

然而，

得到的只有WA，加上了pushdown

还是WA

后来发现是ans的初始值，我偷懒设成了N<<1，结果不够大

所以从中我们可以得到一个结论，

不能偷懒

总之：这次的离散化完成的很好，

doit函数在编写的时候j==n的时候判断不好

线段树常数还是大，

一定要认真读题（不要忘记输出-1）

最后不要偷懒!!!

我发现了一种优化常数的方法

以前我的add函数是这样的

void add(int bh,int l,int r,int z){    if (t[bh].la) push(bh);    if (t[bh].x>=l&&t[bh].y<=r)     {        t[bh].sum+=z;        t[bh].la+=z;        return;    }    int mid=(t[bh].x+t[bh].y)>>1;    if (l<=mid) add(bh<<1,l,r,z);    if (r>mid) add(bh<<1|1,l,r,z);    t[bh].sum=max(t[bh<<1].sum,t[bh<<1|1].sum);}

这次在网上找到了一个dalao的代码，我的代码变成了这样

inline void push(int bh,int z){    t[bh].sum+=z; t[bh].la+=z;} void add(int bh,int l,int r,int z){    if (t[bh].x>=l&&t[bh].y<=r)     {        push(bh,z);        return;    }    if (t[bh].la)    {        push(bh<<1,t[bh].la);        push(bh<<1|1,t[bh].la);        t[bh].la=0;    }    int mid=(t[bh].x+t[bh].y)>>1;    if (l<=mid) add(bh<<1,l,r,z);    if (r>mid) add(bh<<1|1,l,r,z);    t[bh].sum=max(t[bh<<1].sum,t[bh<<1|1].sum);}

一下子就快了2000ms！！！

这里写代码片#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int INF=0x33333333;const int N=1000010;int n,m;struct node{    int x,y,len;};node li[N];int o[N<<1],num[N<<1],tot=0;struct nd{    int x,y,sum,la;};nd t[N<<2];int cmp(const node &a,const node &b){    return a.len
         
          >1;    build(bh<<1,l,mid); build(bh<<1|1,mid+1,r);} inline void push(int bh,int z){    t[bh].sum+=z; t[bh].la+=z;} void add(int bh,int l,int r,int z){    if (t[bh].x>=l&&t[bh].y<=r)     {        push(bh,z);        return;    }    if (t[bh].la)    {        push(bh<<1,t[bh].la);        push(bh<<1|1,t[bh].la);        t[bh].la=0;    }    int mid=(t[bh].x+t[bh].y)>>1;    if (l<=mid) add(bh<<1,l,r,z);    if (r>mid) add(bh<<1|1,l,r,z);    t[bh].sum=max(t[bh<<1].sum,t[bh<<1|1].sum);} void doit() {    int i,j,ans=INF;    bool ff=0;    build(1,1,tot);    j=0;    for (i=1;i<=n;i++)  //枚举区间左端点     {        while (t[1].sum