Luogu

BZOJ

分析

考虑把所有区间按长度从小到大排序,然后枚举最小的区间 $i$,往右扩展到一个 $[i,j]$ 内所有区间包含某个点 $m$ 次的区间 $j$。

这样子的话,显然可以从 $[i,j]$ 中选出 $m$ 个满足条件的区间,于是只要拿 $len_j-len_i$ 更新答案即可。

进一步发现,当 $i$ 增大时 $j$ 是不降的,因此每次可以直接拿上次的 $j$ 来继续扩展。

至于如何判断是否包含某个点 $m$ 次,离散化后拿线段树维护一下区间 $\max$ 值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=1000000+10;

int n,m;

struct interval { int l,r,len; } a[N];
bool operator <(interval a,interval b) { return a.len<b.len;  }

#define ls (o<<1)
#define rs (o<<1|1)
int maxv[N<<2],addv[N<<2];
inline void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
inline void pushdown(int o) {
    if (addv[o]) {
        maxv[ls]+=addv[o],addv[ls]+=addv[o];
        maxv[rs]+=addv[o],addv[rs]+=addv[o];
        addv[o]=0;
    }
}
inline void modify(int o,int l,int r,int ql,int qr,int w) {
    if (ql<=l&&r<=qr) { maxv[o]+=w,addv[o]+=w; return; }
    int mid=(l+r)>>1; pushdown(o);
    if (ql<=mid) modify(ls,l,mid,ql,qr,w);
    if (qr>mid) modify(rs,mid+1,r,ql,qr,w);
    pushup(o);
}
#undef ls
#undef rs

int S[N],top=0;
int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i) {
        S[++top]=a[i].l=read();
        S[++top]=a[i].r=read();
        a[i].len=a[i].r-a[i].l+1;
    }
    sort(S+1,S+top+1); top=unique(S+1,S+top+1)-S-1;
    for (re int i=1;i<=n;++i) {
        a[i].l=lower_bound(S+1,S+top+1,a[i].l)-S;
        a[i].r=lower_bound(S+1,S+top+1,a[i].r)-S;
    }
    sort(a+1,a+n+1); int ans=2e9;
    for (re int i=1,j=0;i<=n;++i) {
        while (j<n&&maxv[1]<m) ++j,modify(1,1,top,a[j].l,a[j].r,1);
        if (maxv[1]>=m) ans=min(ans,a[j].len-a[i].len);
        modify(1,1,top,a[i].l,a[i].r,-1);
    }
    printf("%d\n",ans==2e9?-1:ans);
    return 0;
}
最后修改:2019 年 10 月 17 日 03 : 08 PM