[BZOJ4444][SCOI2015]国旗计划-[ST表]

时间：2023-12-04 14:38:33

Description

传送门

Solution

说真的这道题在场上没做出来的我必定是脑子有洞。。

我们用st表记录以某个位置开始，派了1<<j个战士能到达的最远位置。

由于边境线是一圈，我们把把它当成链并复制一遍，操作的时候注意判断是否覆盖了一圈就好。

PS：边防站是点，它所谓覆盖边境线，是指每一个区间都要有士兵跑。如下图，这可不是每个点有士兵就算了的。

比如说一个士兵在1或3，一个在4或5，看起来非常没有毛病，然而3-4的区间没有人，就不算覆盖了啊啊啊。（不过怕是只有我这种脑袋缺点什么的人才会把它理解成覆盖点吧。。）

1     2     3     4     5

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

using namespace std;

int n,m,l,r,st[][],bin[],ans[];

struct node{int l,r,id;

}a[];int cnt=;

bool cmp(node a,node b){return a.l<b.l;}

int main()

{

    scanf("%d%d",&n,&m);

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

    {

        scanf("%d%d",&l,&r);

        if (l>r) {a[i*-]=node{l,r+m,i};a[i*]=node{l+m,r+*m,};}

        else {a[i*-]=node{l,r,i};a[i*]=node{l+m,r+m,};}

    }

    sort(a+,a+*n+,cmp);

    int now=;

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

    {

        while (a[now+].l<=a[i].r&&now<*n) now++;

        st[i][]=now;

    }

    bin[]=;

    for (int i=;i<=;i++) bin[i]=bin[i-]<<;

    for (int j=;j<=;j++)

        for (int i=;i<=*n-bin[j]+;i++)

            st[i][j]=st[st[i][j-]][j-];

    int tp,cnt;

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

    if (a[i].id)

    {

        tp=a[i].l+m;

        now=i;cnt=;

        for (int j=;j>=;j--)

        if (st[now][j]){

            if (a[st[now][j]].r<tp) now=st[now][j],cnt+=bin[j];

        }

        ans[a[i].id]=cnt;

    }

    for (int i=;i<=n;i++) printf("%d ",ans[i]);

}

相关文章