M_sea

洛谷4155 [SCOI2015]国旗计划
LuoguBZOJ分析首先破环为链。因为不存在区间包含另一个区间的情况,于是可以按$l$排个序,这样子$l$和$r...
扫描右侧二维码阅读全文
31
2019/01

洛谷4155 [SCOI2015]国旗计划

Luogu

BZOJ

分析

首先破环为链。

因为不存在区间包含另一个区间的情况,于是可以按$l$排个序,这样子$l$和$r$都是单调的。

贪心地考虑每段区间的后继,为有交的右端点最靠右的区间。这样子保证区间可以被覆盖,而且用的区间数最少。

求出后继之后,直接暴力统计答案显然不可取。于是用倍增优化一下这个过程就好了。

时间复杂度?应该是$O(n\log n)$的吧...

细节和具体实现见代码。

代码

//It is made by M_sea
#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=400000+10; //两倍空间

int n,m;
int f[21][N],ans[N];
struct node { int l,r,id; } a[N];
bool operator <(const node& a,const node& b) {
    return a.l!=b.l?a.l<b.l:a.r<b.r;
}

int main() {
    n=read(),m=read(); int tot=n;
    for (re int i=1;i<=n;++i) {
        a[i].l=read(),a[i].r=read(),a[i].id=i;
        if (a[i].l>a[i].r) a[i].r+=m; //破环为链
        else a[++tot]=(node){a[i].l+m,a[i].r+m,a[i].id};
    }
    sort(a+1,a+tot+1); a[tot+1].r=2e9; //这里要置个INF
    for (re int i=1,j=1;i<=tot;++i) {
        while (j<=tot&&a[j+1].l<=a[i].r) ++j;
        f[0][i]=j;
    }
    for (re int i=1;i<=20;++i)
        for (re int j=1;j<=tot;++j)
            f[i][j]=f[i-1][f[i-1][j]];
    for (re int i=1;i<=tot;++i) {
        if (a[i].l>m) continue;
        for (re int j=20,p=i;~j;--j)
            if (f[j][p]&&a[f[j][p]].r<a[i].l+m)
                p=f[j][p],ans[a[i].id]+=(1<<j);
        ans[a[i].id]+=2; //把首末也算进去
    }
    for (re int i=1;i<=n;++i) printf("%d%c",ans[i],i==n?'\n':' ');
    return 0;
}
最后修改:2019 年 05 月 26 日 08 : 11 PM

2 条评论

  1. smy

    这题可以O(n)的说(虽然我不会

    1. M_sea
      @smy

      $\texttt{FlashHu}$的神仙做法?

发表评论