bzoj 4653 区间

Posted on | Views:

线段树.

  • 可以先将区间按照大小从小到大排序,并将端点离散化.
  • 枚举以第 $i$ 个区间为最短区间时的答案,从 $i$ 开始往后面添加区间,直到有个点被覆盖 $m$ 次.
  • 更新答案后,下次枚举不需要重新加入,只需要把第 $i$ 个区间删除即可.
  • 用线段树支持区间覆盖与撤销,并维护被覆盖次数的最大值.
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=5e5+10,inf=2e9;
int n,m,ans=inf;
int A[MAXN<<1],cnt=0;
struct interval
{
	int l,r,len;
	bool operator < (const interval &rhs) const
	{
		return len < rhs.len;
	}
}I[MAXN];
int rk(int x)
{
	return lower_bound(A+1,A+1+cnt,x)-A;
}
struct Segtree
{
	struct node
	{
		int tag,mx;
		node(){tag=mx=0;}
	}Tree[MAXN<<3];
#define root Tree[o]
#define lson Tree[o<<1]
#define rson Tree[o<<1|1]
	int query()
	{
		return Tree[1].mx;
	}
	void pushup(int o)
	{
		root.mx=max(lson.mx,rson.mx);
	}
	void modifiy(int o,int c)
	{
		root.tag+=c;
		root.mx+=c;
	}
	void pushdown(int o)
	{
		if(root.tag)
		{
			modifiy(o<<1,root.tag);
			modifiy(o<<1|1,root.tag);
			root.tag=0;
		}
	}
	void upd(int o,int l,int r,int L,int R,int c)
	{
		if(L<=l && r<=R)
		{
			modifiy(o,c);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(o);
		if(L<=mid)
			upd(o<<1,l,mid,L,R,c);
		if(R>mid)
			upd(o<<1|1,mid+1,r,L,R,c);
		pushup(o);
	}
}T;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;++i)
	{
		A[++cnt]=I[i].l=read();
		A[++cnt]=I[i].r=read();
		I[i].len=I[i].r-I[i].l;
	}
	sort(I+1,I+1+n);
	sort(A+1,A+1+cnt);
	cnt=unique(A+1,A+1+cnt)-(A+1);
	for(int i=1;i<=n;++i)
	{
		I[i].l=rk(I[i].l);
		I[i].r=rk(I[i].r);
	}
	int head=1,tail=0;
	while(head<=n)
	{
		while(T.query()<m && tail<n)
		{
			++tail;
			T.upd(1,1,cnt,I[tail].l,I[tail].r,1);
		}
		if(T.query()==m)
			ans=min(ans,I[tail].len-I[head].len);
		T.upd(1,1,cnt,I[head].l,I[head].r,-1);
		++head;
	}
	cout<<(ans==inf?-1:ans)<<endl;
	return 0;
}