BZOJ4653 & 洛谷1712 & UOJ222：[NOI2016]区间—

在数轴上有 n个闭区间 [l1,r1],[l2,r2],...,[ln,rn]。现在要从中选出 m 个区间，使得这 m个区间共同包含至少一个位置。换句话说，就是使得存在一个 x，使得对于每一个被选中的区间 [li,ri]，都有 li≤x≤ri。

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

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

（天哪我终于会做套路题了……虽然对于判断是否合法的时候没想到线段树……）

看复杂度是O(nlogn)猜想可能又是枚举左端点找右端点的套路。

然而相比于一个点被覆盖m次，更难处理的是这个答案的运算。

于是我们将区间按照权值排序，接着就是两个指针不断扩大，当合法的时候更新一下答案就行了。

那么如何维护一个点被最多被覆盖了多少次呢？线段树呗。

注意空间不要开小了-=-

#include<cmath>

#include<stack>

#include<queue>

#include<cstdio>

#include<cctype>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int INF=2e9;

const int N=5e5+;

inline int read(){

    int X=,w=;char ch=;

    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return w?-X:X;

}

struct range{

    int l,r,w;

}g[N];

int n,m,lim,b[*N],tr[*N],lz[*N];

inline bool cmp(range a,range b){

    return a.w<b.w;

}

inline void LSH(){

    sort(b+,b+lim+);

    lim=unique(b+,b+lim+)-b-;

    for(int i=;i<=n;i++){

    g[i].l=lower_bound(b+,b+lim+,g[i].l)-b;

    g[i].r=lower_bound(b+,b+lim+,g[i].r)-b;

    }

}

inline void push(int a){

    if(!lz[a])return;

    lz[a<<]+=lz[a];lz[a<<|]+=lz[a];

    tr[a<<]+=lz[a];tr[a<<|]+=lz[a];

    lz[a]=;

}

void insert(int a,int l,int r,int l1,int r1,int w){

    if(r<l1||r1<l)return;

    if(l1<=l&&r<=r1){

    tr[a]+=w;lz[a]+=w;

    return;

    }

    push(a);

    int mid=(l+r)>>;

    insert(a<<,l,mid,l1,r1,w);

    insert(a<<|,mid+,r,l1,r1,w);

    tr[a]=max(tr[a<<],tr[a<<|]);

}

int main(){

    n=read(),m=read();

    for(int i=;i<=n;i++){

    g[i].l=b[++lim]=read();

    g[i].r=b[++lim]=read();

    g[i].w=g[i].r-g[i].l;

    }

    LSH();

    sort(g+,g+n+,cmp);

    int l=,ans=INF;

    for(int l=,r=;l<=n;l++){

    while(r<n&&tr[]<m){

        r++;

        insert(,,lim,g[r].l,g[r].r,);

    }

    if(tr[]>=m)ans=min(ans,g[r].w-g[l].w);

    insert(,,lim,g[l].l,g[l].r,-);

    }

    printf("%d\n",ans==INF?-:ans);

    return ;

}

+++++++++++++++++++++++++++++++++++++++++++

+本文作者：luyouqi233。　　　　　　　　　　　　　　+

+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+

+++++++++++++++++++++++++++++++++++++++++++

巴特西

BZOJ4653 & 洛谷1712 & UOJ222：[NOI2016]区间——题解

最新文章

热门文章