题目描述
在数轴上有 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],...,[l_n,r_n]$。现在要从中选出 $m$ 个区间，使得这 $m$ 个区间共同包含至少一个位置。换句话说，就是使得存在一个 $x$，使得对于每一个被选中的区间 $[l_i,r_i]$，都有 $l_i le x le r_i$。
对于一个合法的选取方案，它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，即等于它的右端点的值减去左端点的值。
求所有合法方案中最小的花费。如果不存在合法的方案，输出 $−1$。
输入格式
第一行包含两个正整数 $n,m$，用空格隔开，意义如上文所述。保证 $1 le m le 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了，那么，从前往后开始删除，这样，每次取得的代价的最小值，显然就是最后的答案
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#include<map>
#define LL long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
return *p1++;
}
inline void read(int &x){
char c=nc();int b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline void read(LL &x){
char c=nc();LL b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
inline int read(char *s)
{
char c=nc();int len=0;
for(;!(c>='a' && c<='z');c=nc()) if (c==EOF) return 0;
for(;(c>='a' && c<='z');s[len++]=c,c=nc());
s[len++]=' ';
return len;
}
inline void read(char &x){
for (x=nc();!(x>='A' && x<='Z');x=nc());
}
int wt,ss[19];
inline void print(int x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {
for (wt=0;x;ss[++wt]=x%10,x/=10);
for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
if (x<0) x=-x,putchar('-');
if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
int n,m,k,b[1000010];
struct data
{
int x,y,l;
}a[500010];
struct ST
{
int x,tag;
}tree[4000010];
bool cmp(data x,data y)
{
return x.l<y.l;
}
int Hash(int x)
{
return lower_bound(b+1,b+1+k,x)-b;
}
void Pushdown(int x)
{
if (tree[x].tag!=0)
{
tree[x<<1].tag+=tree[x].tag;
tree[x<<1|1].tag+=tree[x].tag;
tree[x].tag=0;
}
}
void change(int lq,int rq,int l,int r,int x,int z)
{
if (lq<=l && rq>=r) {tree[x].tag+=z;return ;}
int mid=l+r>>1;
Pushdown(x);
if (lq<=mid) change(lq,rq,l,mid,x<<1,z);
if (rq>mid) change(lq,rq,mid+1,r,x<<1|1,z);
tree[x].x=max(tree[x<<1].x+tree[x<<1].tag,tree[x<<1|1].tag+tree[x<<1|1].x);
}
int main()
{
read(n);read(m);
k=0;
for (int i=1;i<=n;i++)
read(a[i].x),read(a[i].y),a[i].l=a[i].y-a[i].x,b[++k]=a[i].x,b[++k]=a[i].y;
sort(a+1,a+1+n,cmp);
sort(b+1,b+1+k);
k=unique(b+1,b+1+k)-b-1;int l=0,t,ans=INT_MAX;
for (int i=1;i<=n;i++)
{
change(Hash(a[i].x),Hash(a[i].y),1,k,1,1);
t=0;
while (tree[1].x+tree[1].tag>=m)
{
l++;t=1;
change(Hash(a[l].x),Hash(a[l].y),1,k,1,-1);
}
if (t==1) change(Hash(a[l].x),Hash(a[l].y),1,k,1,1);
if (tree[1].x+tree[1].tag==m)
ans=min(ans,a[i].l-a[l].l);
l--;
}
if (ans==INT_MAX) puts("-1");else print(ans),puts("");
return 0;
}