「NOI2016」区间

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

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

输出格式

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

数据范围与提示

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

测试点编号 $ 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 $

首先容易想到对区间按长度进行排序，然后枚举最长和最短的区间（下面称为“起点”、“终点”）。这样的话还需要选择的$m-2$个区间只能在两个区间当中的选。判断合法也很简单：如果存在某个位置不仅在起点和终点的交集当中，而且被起点和终点之间的区间覆盖的次数不小于$m-2$次，那么就是合法的一种起点和终点。用线段树处理区间覆盖问题，时间复杂度$O(n^2logn)$，能拿60分。

考虑改进上述算法。在上面的过程中，容易发现有的位置可能被覆盖了$m$次或者更多，但是并不在起点与终点的交集当中，这意味着什么呢？这说明如果把新的起点设为某个在起点和终点之间的点能得到一组合法的、不会更劣的解。因此，如果我们在处理区间覆盖时，在第一次出现某个位置被覆盖了$m$次或者更多时更新答案，更新完之后移动起点，那么下一次的终点一定是不降的，而且这样做一定能把最优解包含在其中，所以复杂度为$O(nlogn)$，可以通过本题。

采用zkw线段树可以获得较小的常数。

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
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define MAXN 1000005
#define MAXT 8000005
using namespace std;

char *p1,*p2,buf[1<<20];
#define GC (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?0:*p1++)
inline int _R(){
	int v=0;char s=GC;
	while(s>57||s<48)s=GC;
	for(;s>47&&s<58;s=GC)v=v*10+s-48;
	return v;
}

struct node{
	int l,r,ll,rr,len;
}A[MAXN];
bool operator<(node a,node b){return a.len<b.len;}

int N,M,Ans=2e9,Hash[MAXN];
int n,m,mx[MAXT];

void update(int p){
	if(!p)return;
	int ls=p<<1,rs=ls|1,v=mx[ls]>mx[rs]?mx[ls]:mx[rs];
	mx[p]+=v;mx[ls]-=v;mx[rs]-=v;
}

void modify(int l,int r,int k){
	for(l+=m-1,r+=m+1;l^r^1;){
		if(~l&1)mx[l^1]+=k;
		if(r&1)mx[r^1]+=k;
		l>>=1;r>>=1;
		update(l);update(r);
	}
	while(l)update(l),l>>=1;
}

int main(){
	int i,l,r;
	N=_R();M=_R();
	for(i=1;i<=N;i++){
		l=_R();r=_R();
		A[i].l=l;A[i].r=r;A[i].len=r-l;
		Hash[++Hash[0]]=l;
		Hash[++Hash[0]]=r;
	}
	
	sort(A+1,A+N+1);
	sort(Hash+1,Hash+Hash[0]+1);
	n=unique(Hash+1,Hash+Hash[0]+1)-Hash-1;
	for(i=1;i<=N;i++){
		A[i].ll=lower_bound(Hash+1,Hash+n+1,A[i].l)-Hash;
		A[i].rr=lower_bound(Hash+1,Hash+n+1,A[i].r)-Hash;
	}
	
	m=1;while(m<=n)m<<=1;
	
	for(l=1,r=0;l<=N;l++){
		if(l>1)modify(A[l-1].ll,A[l-1].rr,-1);
		if(mx[1]>=M){Ans=min(Ans,A[r].len-A[l].len);continue;}
		while(r<l)r++,modify(A[r].ll,A[r].rr,1);
		while(mx[1]<M&&r<N)r++,modify(A[r].ll,A[r].rr,1);
		if(mx[1]>=M)Ans=min(Ans,A[r].len-A[l].len);
	}
	
	if(Ans!=2e9)printf("%d\n",Ans);
	else puts("-1");
}