NOI2016 区间

发表于 | 分类于

NOI2016区间

在数轴上有$ n $个闭区间 $[l_1,r_1],[l_2,r_2],…,[l_n,r_n]$。现在要从中选出 $m $个区间，使得这$ m $个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$，使得对于每一个被选中的区间$ [l_i,r_i]$，都有 $l_i≤x≤r_i$。

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

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

输入格式

第一行包含两个正整数$ n,m$，用空格隔开，意义如上文所述。保证$ 1≤m≤n$。

接下来 $n$行，每行表示一个区间，包含用空格隔开的两个整数 $l_i $和 $r_i$ 为该区间的左右端点。

输出格式

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

样例

input

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

output

2

数据范围与约定
$ n<=500000,m<=200000$

时间限制：3s
空间限制：256MB

题解

这题暴力还是很好打的，$O(n^2logn)$+离散化可以水过去60分。具体就是枚举重叠的是哪一个点然后暴力计算出哪些区间可以选，然后排序贪心地选连续的$m$个即可。

正解是用线段树维护。离散化之后，将区间按长度排序，我们可以发现在选择的时候，枚举一个最小和一个最大，即一个左指针，一个右指针，然后可以发现，我们可以用线段树维护每个点被几个区间覆盖了，然后对于线段树维护的全局最大值，如果当前大于$m$，则可以直接在当前选的区间范围内的右端点减去左端点就是当前的$ans$，持续更新即可。

复杂度$O(nlogn)$。

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
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
#include<cstdio>
   #include<vector>
   #include<algorithm>
   #include<cstring>
   #include<iostream>
   using namespace std;
   const int N=5e5+1e3+7;
   struct T{
       int ls,rs,mx,l,r,tag;
   }t[N*4+1];
   struct node{
       int len,l,r;
   }rg[N*2+1];
   int n,m,x[N],y[N],w[N*2+1],ans=0x7fffffff,now[N],cnt,root;
   void update(int now)
   {
       int ls=t[now].ls,rs=t[now].rs;
       t[now].mx=max(t[ls].mx,t[rs].mx);
   }
   void pushdown(int now)
   {
       int ls=t[now].ls,rs=t[now].rs;
       if(ls)
       {
           t[ls].mx+=t[now].tag;
           t[ls].tag+=t[now].tag;
       }
       if(rs)
       {
           t[rs].mx+=t[now].tag;
           t[rs].tag+=t[now].tag;
       }
       t[now].tag=0;
   }
   int build(int l,int r)
   {
       int now=++cnt;
       int mid=(l+r)>>1;
       t[now].l=l,t[now].r=r;
       if(l==r)
           return cnt;
       t[now].ls=build(l,mid);
       t[now].rs=build(mid+1,r);
       return now;
   }
   void add(int now,int l,int r,int val)
   {
       pushdown(now);
       if(t[now].l>=l&&t[now].r<=r)
       {
           t[now].mx+=val;
           t[now].tag+=val;
           return;
       }
       int mid=(t[now].l+t[now].r)>>1;
       if(l<=mid)
           add(t[now].ls,l,r,val);
       if(r>mid)
           add(t[now].rs,l,r,val);
       update(now);
   }
   bool cmp(node a,node b)
   {
       return a.len<b.len;
   }
   int main()
   {
       scanf("%d%d",&n,&m);
       for(int i=1;i<=n;i++)
           scanf("%d%d",&x[i],&y[i]);
       for(int i=1;i<=n;i++)
           w[i*2-1]=x[i],w[i*2]=y[i];
       sort(w+1,w+2*n+1);
       for(int i=1;i<=n;i++)
           rg[i].l=lower_bound(w+1,w+n*2+1,x[i])-w,rg[i].r=lower_bound(w+1,w+n*2+1,y[i])-w,rg[i].len=y[i]-x[i];
       sort(rg+1,rg+n+1,cmp);
       root=build(1,n*2+1);
       add(root,rg[1].l,rg[1].r,1);
       int ll=1,rr=2;
       while(ll<=n)
       {
           while(rr<=n&&t[root].mx<m)
           {
               add(root,rg[rr].l,rg[rr].r,1);
                   rr++;
           }
           if(t[root].mx<m)
               break;
           ans=min(ans,rg[rr-1].len-rg[ll].len);
           add(root,rg[ll].l,rg[ll].r,-1);
           ll++;
       }
       if(ans!=0x7fffffff)
           printf("%d",ans);
       else
           printf("-1");
   }