题意描述

在数轴上有 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],…,[l_n,r_n]$。

现在要从中选出 $m$ 个区间，使得这 $m$ 个区间共同包含至少一个位置。

换句话说，就是使得存在一个 $x$，使得对于每一个被选中的区间 $[l_i,r_i]$，都有 $l_i\leq x\leq r_i$。

对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 $[l_i,r_i]$ 的长度定义为 $r_i−l_i$，即等于它的右端点的值减去左端点的值。

求所有合法方案中最小的花费。如果不存在合法的方案，输出 $−1$。

输入格式

第一行包含两个正整数 $n,m$ 用空格隔开，意义如上文所述。保证 $1\leq m\leq n$。

接下来 $n$ 行，每行表示一个区间，包含用空格隔开的两个整数 $l_i$ 和 $r_i$ 为该区间的左右端点。

输出格式

只有一行，包含一个正整数，即最小花费。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

样例解释

如图，当 $n=6,m=3$ 时，花费最小的方案是选取 $[3,5]$、$[3,4]$、$[1,4]$ 这三个区间，他们共同包含了 $4$ 这个位置，所以是合法的。其中最长的区间是 $[1,4]$，最短的区间是 $[3,4]$，所以它的花费是 $(4−1)−(4−3)=2$。

数据范围和约定

测试点编号	$ n $	$ m $	$ l_i,r_i $
1	$ 20 $	$ 9 $	$ 0 \le l_i \le r_i \le 100 $
2	$ 20 $	$ 10 $	$ 0 \le l_i \le r_i \le 100 $
3	$ 199 $	$ 3 $	$ 0 \le l_i \le r_i \le 100000 $
4	$ 200 $	$ 3 $	$ 0 \le l_i \le r_i \le 100000 $
5	$ 1000 $	$ 2 $	$ 0 \le l_i \le r_i \le 100000 $
6	$ 2000 $	$ 2 $	$ 0 \le l_i \le r_i \le 100000 $
7	$ 199 $	$ 60 $	$ 0 \le l_i \le r_i \le 5000 $
8	$ 200 $	$ 50 $	$ 0 \le l_i \le r_i \le 5000 $
9	$ 200 $	$ 50 $	$ 0 \le l_i \le r_i \le 10^9 $
10	$ 1999 $	$ 500 $	$ 0 \le l_i \le r_i \le 5000 $
11	$ 2000 $	$ 400 $	$ 0 \le l_i \le r_i \le 5000 $
12	$ 2000 $	$ 500 $	$ 0 \le l_i \le r_i \le 10^9 $
13	$ 30000 $	$ 2000 $	$ 0 \le l_i \le r_i \le 100000 $
14	$ 40000 $	$ 1000 $	$ 0 \le l_i \le r_i \le 100000 $
15	$ 50000 $	$ 15000 $	$ 0 \le l_i \le r_i \le 100000 $
16	$ 100000 $	$ 20000 $	$ 0 \le l_i \le r_i \le 100000 $
17	$ 200000 $	$ 20000 $	$ 0 \le l_i \le r_i \le 10^9 $
18	$ 300000 $	$ 50000 $	$ 0 \le l_i \le r_i \le 10^9 $
19	$ 400000 $	$ 90000 $	$ 0 \le l_i \le r_i \le 10^9 $
20	$ 500000 $	$ 200000 $	$ 0 \le l_i \le r_i \le 10^9 $

分析

$\text{NOI}$ 签到题无疑了……

考虑朴素做法：先将区间从小到大排序，然后按照排序后的顺序依次加入。

若有一个点的覆盖次数大于$m$，则记录答案并依次将前面插入的区间删除，直到小于$m$为止。

不难看出，这利用了尺取法的思想。

但这种做法的瓶颈在于如何快速查询是否有一个点的覆盖次数大于$m$。很明显，这可以使用线段树维护区间最大值解决。

然后就做完了。

顺便提一句，$l , r$的范围很大，需要离散化一下。

剩下的见代码注释。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define ll long long
#define pb push_back
#define MP make_pair
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 500011;
const int HA = 998244353;
const int INF = 2047483647;
const long long INFL = 9023372036854775807;

struct Line{
    int l , r , len;
}line[M];

bool cmp(Line a , Line b){
    return a.len < b.len;
}

int a[M << 1] , cnt;

int input(int n){   
    //离散化，返回值为所有线段中最右边的端点。因为建树时需要用到
    int maxn = -1;
    rep(i , 1 , n){
        scanf("%d%d" , &line[i].l , &line[i].r);
        line[i].len = line[i].r - line[i].l;
        a[++ cnt] = line[i].l;
        a[++ cnt] = line[i].r;
    }
    sort(a + 1 , a + 1 + cnt);
    cnt = unique(a + 1 , a + 1 + cnt) - a - 1;
    rep(i , 1 , n){
        line[i].l = lower_bound(a + 1 , a + 1 + cnt , line[i].l) - a;
        line[i].r = lower_bound(a + 1 , a + 1 + cnt , line[i].r) - a;
        maxn = max(maxn , line[i].r);
    }
    return maxn;
}

namespace Segment_tree{
    #define lson(x) x << 1
    #define rson(x) x << 1 | 1

    struct Node{
        int l , r , len;
        int num , add , maxn;
    }node[M << 2];

    I void pushup(int x){
        node[x].num = node[lson(x)].num + node[rson(x)].num;
        node[x].maxn = max(node[lson(x)].maxn , node[rson(x)].maxn);
    }

    I void pushdown(int x){
        if(!node[x].add) return ;
        node[lson(x)].add += node[x].add;
        node[lson(x)].num += node[x].add * node[lson(x)].len;
        node[lson(x)].maxn += node[x].add;
        node[rson(x)].add += node[x].add;
        node[rson(x)].num += node[x].add * node[rson(x)].len;
        node[rson(x)].maxn += node[x].add;
        node[x].add = 0;
    }

    void build(int x , int l , int r){
        node[x].l = l , node[x].r = r , node[x].len = (r - l + 1);
        if(l == r){
            node[x].num = 0;
            node[x].maxn = 0;
            return ;
        }
        int mid = (l + r) >> 1;
        build(lson(x) , l , mid); 
        build(rson(x) , mid + 1 , r);
        pushup(x);
    }

    void range_add(int x , int ql , int qr , int add){
        if(ql <= node[x].l && node[x].r <= qr){
            node[x].add += add;
            node[x].maxn += add;
            node[x].num += add * (node[x].len);
            return ;
        }
        pushdown(x);
        int mid = (node[x].l + node[x].r) >> 1;
        if(ql <= mid){
            range_add(lson(x) , ql , qr , add);
        }
        if(mid + 1 <= qr){
            range_add(rson(x) , ql , qr , add);
        }
        pushup(x);
    }

    #undef lson
    #undef rson
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n , m; scanf("%d%d" , &n , &m);
    int maxn = input(n);
    sort(line + 1 , line + 1 + n , cmp);
    int ans = 0x3f3f3f3f;
    Segment_tree :: build(1 , 1 , maxn);
    int l = 1 , r = 1;
    for(r = 1; r <= n; r ++){   //尺取模板
        Segment_tree :: range_add(1 , line[r].l , line[r].r , 1);
        while(Segment_tree :: node[1].maxn >= m){   
            //node[1]代表整个区间，因此node[1]的max为整个区间的最大值。
            ans = min(ans , line[r].len - line[l].len);
            Segment_tree :: range_add(1 , line[l].l , line[l].r , -1);
            l ++;
        }
    }
    if(ans == 0x3f3f3f3f) puts("-1");
    else printf("%d\n" , ans);
    
    return 0;
}