NOI2016 区间（线段树）

发表于 |
字数统计: 1,005字 | 阅读时长 ≈ 5min

【NOI2016】区间

问题描述

在数轴上有 $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$ 为该区间的左右端点。

输出格式

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

样例输入

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

样例输出

2

提示

所有测试数据的范围和特点如下表所示：






测试点编号 $ n $ $ m $ $ l_i,r_i $
1 $ 20 $ $ 9 $ $ 0 \le l_i \le r_i \le 100 $
2 $ 10 $
3 $ 199 $ $ 3 $ $ 0 \le l_i \le r_i \le 100000 $
4 $ 200 $
5 $ 1000 $ $ 2 $
6 $ 2000 $
7 $ 199 $ $ 60 $ $ 0 \le l_i \le r_i \le 5000 $
8 $ 200 $ $ 50 $
9 $ 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 $
12 $ 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 $
15 $ 50000 $ $ 15000 $
16 $ 100000 $ $ 20000 $
17 $ 200000 $ $ 0 \le l_i \le r_i \le 10^9 $
18 $ 300000 $ $ 50000 $
19 $ 400000 $ $ 90000 $
20 $ 500000 $ $ 200000 $

首先将区间按照长度排序，那么不难发现最后答案一定可以由连续的一段区间给出。然后判断一段区间$[l,r]$是否合法就是判断将这些区间拿去做区间覆盖之后有一个位置的覆盖次数大于等于$m$，容易发现对于每一个$r$作为右端点的时候，最优的$l$的取值一定是单调不降的。

因此我们可以从左往右枚举$r$，然后维护最优的$l$的位置，当$[l,r]$满足条件时就更新答案。只需要用一颗线段树来维护区间覆盖就行了。

代码：

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
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 1000005
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
char buf[1<<20],*p1,*p2;
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline void _R(int &x)
{
	char t=GC;
	while(t<48||t>57)t=GC;
	for(x=0;t>47&&t<58;t=GC)x=(x<<3)+(x<<1)+t-48;
}
struct nodd
{
	int l,r;
	bool operator<(const nodd &b)const
	{return r-l<b.r-b.l;}
}K[N];
int n,m,ans=1e9,T,Hash[N];
int Max[N<<2],lazy[N<<2],ux,uy,ud;
void ADD(register int p,register int l,register int r)
{
	if(ux<=l&&uy>=r){Max[p]+=ud;lazy[p]+=ud;return;}
	register int mid=l+r>>1;
	if(ux<=mid)ADD(p<<1,l,mid);
	if(uy>mid)ADD(p<<1|1,mid+1,r);
	Max[p]=max(Max[p<<1],Max[p<<1|1]);
	Max[p]+=lazy[p];
}
int main()
{
	int i,j,k,x,y;
	_R(n);_R(m);
	for(i=1;i<=n;i++)
	{
		_R(x);_R(y);
		Hash[++T]=x;Hash[++T]=y;
		K[i]=(nodd){x,y};
	}
	sort(K+1,K+n+1);
	sort(Hash+1,Hash+T+1);
	T=unique(Hash+1,Hash+T+1)-Hash-1;
	for(i=1;i<=n;i++)
	{
		K[i].l=lower_bound(Hash+1,Hash+T+1,K[i].l)-Hash;
		K[i].r=lower_bound(Hash+1,Hash+T+1,K[i].r)-Hash;
	}
	for(i=j=1;i<=n;i++)
	{
		ux=K[i].l;uy=K[i].r;ud=1;
		ADD(1,1,T);
		while(Max[1]>=m)
		{
			ans=min(ans,Hash[K[i].r]-Hash[K[i].l]-Hash[K[j].r]+Hash[K[j].l]);
			ux=K[j].l;uy=K[j].r;ud=-1;
			ADD(1,1,T);j++;
		}
	}
	printf("%d",ans==1e9?-1:ans);
}