区间

Time Limit: 60 Sec Memory Limit: 256 MB

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 为该区间的左右端点。

Output

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

Sample Input

6 3
　3 5
　1 2
　3 4
　2 2
　1 5
　1 4

Sample Output

2

HINT

N<=500000,M<=200000,0≤li≤ri≤10^9

Main idea

给定若干个区间，取出m个若这m个包含同一个位置则可以统计值，值为这m个中的最大区间长度减去最小区间长度，输出最小值。

Solution

发现答案为最大区间长度减去最小区间长度，显然可以先按照长度排序，然后枚举左端点（即最小区间长度），中间小于最大区间长度的区间的加入 只会使得更可能满足条件 而不会影响答案，所以我们用r表示当前加入到了右端点r这个位置，r显然递增，则可以用r一直往后推到满足条件了更新答案，用线段树维护区间+1。因为l[i]与r[i]长度较大，但是发现非常长的长度是不会影响是否可以统计的（因为满足统计的条件只要符合个数>=m即可），所以我们可以对l和r离散化。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include<bits/stdc++.h>
using namespace std;

const int ONE=1000001;
const int INF=2147483640;

int n,m;
int Ans,res;
int num,cnt;

struct lisan
{
    int pos;
    int value;
}Q[ONE*2];

struct point
{
    int l,r;
    int value;
}a[ONE];

struct power
{
    int value;
    int add;
}Node[ONE*4];

int cmp(const point &a,const point &b)
{
    return a.value<b.value;
}

int rule(const lisan &a,const lisan &b)
{
    return a.value<b.value;
}

void pushdown(int i)
{
    if(Node[i].add)
    {
        Node[i*2].add+=Node[i].add;
        Node[i*2+1].add+=Node[i].add;
        Node[i*2].value+=Node[i].add;
        Node[i*2+1].value+=Node[i].add;
        Node[i].add=0;
    }
}

void Update(int i,int l,int r,int L,int R,int x)
{
    if(L<=l && r<=R)
    {
        Node[i].add+=x;
        Node[i].value+=x;
        return;
    }
    pushdown(i);

    int mid=(l+r)/2;
    if(L<=mid) Update(i*2,l,mid,L,R,x);
    if(mid+1<=R) Update(i*2+1,mid+1,r,L,R,x);
    Node[i].value=max(Node[i*2].value,Node[i*2+1].value);
}

int get()
{
    int res,Q=1;    char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Getlisan()
{
    for(int i=1;i<=n;i++)
    {
        Q[++num].value=a[i].l; Q[num].pos=num;
        Q[++num].value=a[i].r; Q[num].pos=num;
    }

    sort(Q+1,Q+num+1,rule);
    Q[0].value=-1;
    for(int i=1;i<=num;i++)
    {
        if(Q[i].value!=Q[i-1].value) cnt++;
        int x=(Q[i].pos+1)/2;
        if(Q[i].pos % 2) a[x].l=cnt;
        else a[x].r=cnt;
    }

    sort(a+1,a+n+1,cmp);
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
    {
        a[i].l=get();    a[i].r=get();
        a[i].l++;    a[i].r++;
        a[i].value=a[i].r-a[i].l;
    }
    Getlisan();

    int r=0;
    Ans=INF;
    for(int i=1;i<=n;i++)
    {
        for(;;)
        {
            if(Node[1].value>=m || (r+1)>n) break;
            r++;
            Update(1,1,cnt,a[r].l,a[r].r,1);
        }
        if(Node[1].value>=m)
            Ans=min(Ans,a[r].value-a[i].value);

        Update(1,1,cnt,a[i].l,a[i].r,-1);
    }

    if(Ans==INF) printf("-1");
    else printf("%d",Ans);
}