#P4653. [Noi2016]区间

    ID: 2870 传统题 6000ms 256MiB 尝试: 1657 已通过: 738 难度: 6 上传者: 标签>难度分类提高+/省选-排序与序列处理尺取法离散化数据结构懒标记线段树CF2100

[Noi2016]区间

[NOI2016] 区间

题目描述

在数轴上有 nn 个闭区间从 11 至 nn 编号,第 ii 个闭区间为 [li,ri][l_i,r_i] 。

现在要从中选出 mm 个区间,使得这 mm 个区间共同包含至少一个位置。换句话说,就是使得存在一个 xx ,使得对于每一个被选中的区间 [li,ri][l_i,r_i],都有 li≤x≤ril_i \leq x \leq r_i 。

对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。

区间 [li,ri][l_i,r_i] 的长度定义为 (ri−li)(r_i-l_i) ,即等于它的右端点的值减去左端点的值。

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

输入格式

第一行包含两个整数,分别代表 nn 和 mm。

第 22 到第 (n+1)(n + 1) 行,每行两个整数表示一个区间,第 (i+1)(i + 1) 行的整数 li,ril_i, r_i 分别代表第 ii 个区间的左右端点。

输出格式

输出一行一个整数,表示最小花费。无合法选取方案时输出 −1-1。

样例 1

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

样例 2

9 4
2 5
1 7
6 7
1 4
3 5
0 8
1 7
1 2
9 10
3

样例 3

输入 · 输出

提示

样例 1 解释

样例 1 中的六个闭区间及其在数轴上的位置

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

数据范围

本题共 20 个测试点,各测试点信息如下表。

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

对于全部的测试点,保证 1≤m≤n1 \leq m \leq n,1≤n≤5×1051 \leq n \leq 5 \times 10^5,1≤m≤2×1051 \leq m \leq 2 \times 10^5,0≤li≤ri≤1090 \leq l_i \leq r_i \leq 10^9。