「LOJ 2086」「NOI2016」区间

发表于

在数轴上有 nn 个闭区间 [l1,r1],[l2,r2],...,[ln,rn][l_1,r_1],[l_2,r_2],...,[l_n,r_n] 。现在要从中选出 mm 个区间，使得这 mm 个区间共同包含至少一个位置。换句话说，就是使得存在一个 xx，使得对于每一个被选中的区间 [li,ri][l_i,r_i] 。

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

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

Constraints

n≤500000n \leq 500000 ， m≤200000m \leq 200000 ， 0≤li≤ri≤1090 \leq l_i \leq r_i \leq 10^9

Solution

将区间按长度排序，然后观察可得，答案一定是在覆盖了同一个点连续的 mm 个区间里。所以可以按顺序用线段树维护一个点被覆盖的次数，当覆盖次数达到 mm 时更新答案，移动头指针并撤销影响。区间端点需要离散化。

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
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
#define lc (x<<1)
#define rc (x<<1|1)
using namespace std;
const int N=5e5+5;
int n,m,cnt,L,R;
int x[N*2],s[N*8],tag[N*8];
struct node{int l,r,len;}a[N];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
bool cmp(node a,node b){return a.len<b.len;}
void down(int x)
{
	s[lc]+=tag[x];tag[lc]+=tag[x];
	s[rc]+=tag[x];tag[rc]+=tag[x];
	tag[x]=0;
}
void modify(int x,int l,int r,int val)
{
	if(tag[x]&&l!=r)down(x);
	if(L<=l&&r<=R){s[x]+=val;tag[x]+=val;return;}
	int mid=(l+r)>>1;
	if(L<=mid)modify(lc,l,mid,val);
	if(R>mid)modify(rc,mid+1,r,val);
	s[x]=max(s[lc],s[rc]);
}
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
	{
		a[i].l=read();a[i].r=read();
		x[++cnt]=a[i].l;x[++cnt]=a[i].r;
		a[i].len=a[i].r-a[i].l;
	}
	sort(a+1,a+n+1,cmp);
	sort(x+1,x+cnt+1);
	cnt=unique(x+1,x+cnt+1)-x-1;
	for(int i=1;i<=n;i++)
		a[i].l=lower_bound(x+1,x+cnt+1,a[i].l)-x,
		a[i].r=lower_bound(x+1,x+cnt+1,a[i].r)-x;
	int head=1,tail=1,ans=0x3f3f3f3f;
	while(tail<=n)
	{
		L=a[tail].l;R=a[tail].r;modify(1,1,cnt,1);
		while(s[1]>=m)
		{
			ans=min(ans,a[tail].len-a[head].len);
			L=a[head].l;R=a[head].r;
			modify(1,1,cnt,-1);head++;
		}
		tail++;
	}
	printf("%d\n",ans!=0x3f3f3f3f?ans:-1);
	return 0;
}