题面

https://www.luogu.com.cn/problem/P4155

问在环上最少取多少个区间能完全覆盖环

分析

首先发现是环，先把端点变为2n方便处理，注意离散化

其次要删去贡献不如其他区间，也就是被包含的区间

考虑朴素做法，在删去被包含区间后，若按左端点排序，右端点也必然递增，那么确定出发点后即可O(n)地向后选择相交区间，直到选回初始区间为止

注意到在贪心选择与当前相交的区间相交的右端点最远的区间时，构成了唯一对应的关系，考虑用倍增优化选择，获得答案的时间降至O(logn)

枚举起始区间即可

代码

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

using namespace std;

const int N=2e5+10;

struct Wiors {

    int c,d,id;

}t[2*N];

int n,m;

int f[2*N][20],l,ans[N];

bool CMP(Wiors a,Wiors b) {return a.c<b.c;}

int Calc(int x) {

    int ans=2,cir=t[x].c+m-1;

    for (int i=l,s=1<<l;i>=0;i--,s>>=1)

        if (f[x][i]&&t[f[x][i]].d<=cir) x=f[x][i],ans+=s;

    return ans;

}

int main() {

    scanf("%d%d",&n,&m);l=log2(n)+1;

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

        scanf("%d%d",&t[i].c,&t[i].d);

        if (t[i].d<t[i].c) t[i].d+=m;

        t[i].id=i;t[i+n]=t[i];t[n+i].c+=m;t[n+i].d+=m;

    }

    sort(t+1,t+2*n+1,CMP);

    for (int i=1,j=1;i<=2*n;i++) {

        while (t[i].d>=t[j].c&&j<=2*n) j++;j--;

        f[i][0]=j;

    }

    for (int i=1;i<=l;i++)

        for (int j=1;j<=2*n;j++) f[j][i]=f[f[j][i-1]][i-1];

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

        ans[t[i].id]=Calc(i);

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

}

巴特西

[倍增]luogu P4155 [SCOI2015]国旗计划

题面

分析

代码

最新文章

热门文章