BZOJ-4653: [Noi2016]区间

[文章目录]

Description

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间,使得这 m个区间共同包含至少一个位置。换句话说,就是使得存在一个 x,使得对于每一个被选中的区间 [li,ri],都有 li≤x≤ri。对于一个合法的选取方案,它的花费为被选中的最长区间长度减去被选中的最短区间长度。区间 [li,ri] 的长度定义为 ri−li,即等于它的右端点的值减去左端点的值。求所有合法方案中最小的花费。如果不存在合法的方案,输出 −1。

性质:一个区间集合合法,包含这个区间集合的大集合也合法。
将区间按照长度排序,双指针枚举答案区间,线段树判断是否合法更新答案。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 501000 
const int inf=0x3f3f3f3f;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x=0; char ch=nc();
    while(!isdigit(ch)) ch=nc();
    while(isdigit(ch)) x=x*10+(ch^'0'),ch=nc();
    return x;
}
int n,m,ans=inf,b[N<<1],c[N<<1],L[N],R[N],tot;
struct node
{
    int l,r;
}a[N];
bool cmp(node x,node y){return (x.r-x.l)<(y.r-y.l);}

int mx[N<<3],lz[N<<3];
inline int Max(int x,int y){return x>y?x:y;}
void pushdown(int pos)
{
    if(lz[pos])
    {
        lz[pos<<1]+=lz[pos]; mx[pos<<1]+=lz[pos];
        lz[pos<<1|1]+=lz[pos]; mx[pos<<1|1]+=lz[pos];
        lz[pos]=0;
    }
}
void fix(int pos,int l,int r,int x,int y,int z)
{
    if(x<=l&&y>=r)
    {
        mx[pos]+=z; lz[pos]+=z;
        return ;
    }
    int mid=(l+r)>>1; pushdown(pos);
    if(x<=mid) fix(pos<<1,l,mid,x,y,z);
    if(y>mid) fix(pos<<1|1,mid+1,r,x,y,z);
    mx[pos]=Max(mx[pos<<1],mx[pos<<1|1]);
}

int main()
{
    n=read(); m=read();
    int i;
    for(i=1;i<=n;++i) a[i].l=b[i]=read(),a[i].r=b[i+n]=read();
    sort(b+1,b+2*n+1);
    sort(a+1,a+n+1,cmp);
    for(c[++tot]=b[1],i=2;i<=n*2;++i)
        if(b[i]!=b[i-1])
            c[++tot]=b[i];
    int l=1;
    for(i=1;i<=n;++i)
    {
        L[i]=lower_bound(c+1,c+tot+1,a[i].l)-c;
        R[i]=lower_bound(c+1,c+tot+1,a[i].r)-c;
        fix(1,1,tot,L[i],R[i],1);
        if(mx[1]>=m)
        {
            while(mx[1]>=m)
            {
                fix(1,1,tot,L[l],R[l],-1);
                ++l;
            }
            --l;
            fix(1,1,tot,L[l],R[l],1);
            ans=min(ans,(a[i].r-a[i].l)-(a[l].r-a[l].l));
        }
    }
    if(ans==inf) puts("-1");
    else printf("%d\n",ans);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注