洛谷4155 [SCOI2015]国旗计划

题意

环上有 $m(\le 10^9)$ 个点，有 $n(\le 2\times 10^5)$ 个人可以从 $l_i\rightarrow r_i$ 。对于所有的 $i\in [1,n]$ ，询问如果第 $i$ 个人必须选且为起点，至少要选多少人才能绕完一圈。

题解

首先断环成链。容易想到贪心，每次选 $l_i\le $ 当前的 $r$ ，$r_i$ 最大的 $i$ 作为下一步。

一步一步跳是 $O(n^2)$ 的，不过可以用倍增预处理出 $f[i][j]$ ，表示第 $i$ 个人跳 $2^j$ 步后到哪，这样就可以在 $O(n\log n)$ 内得到答案。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

const int N=200005;
struct node {
    int l,r,id;
} s[N<<1];
int n,m,f[N<<1][20],ans[N];

inline bool cmp(const node &x,const node &y) { return x.l<y.l; }

signed main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        s[i].l=read(); s[i].r=read(); s[i].id=i;
        if (s[i].l>s[i].r) s[i].r+=m;
    }
    sort(s+1,s+n+1,cmp);
    for (int i=1;i<=n;i++) s[i+n].l=s[i].l+m,s[i+n].r=s[i].r+m; //断环成链
    n<<=1;
    for (int i=1,j=2;i<=n;i++) //预处理出走一步到哪
    {
        for (;j<=n && s[j].l<=s[i].r;j++);
        f[i][0]=j-1;
    }
    for (int j=1;j<=19;j++) for (int i=1;i<=n;i++) f[i][j]=f[f[i][j-1]][j-1]; //倍增
    n>>=1;
    for (int i=1;i<=n;i++)
    {
        int r=s[i].l+m,k=i;
        for (int j=19;~j;j--)
        {
            if (f[k][j] && s[f[k][j]].r<r)
            {
                k=f[k][j];
                ans[s[i].id]|=1<<j;
            }
        }
        ans[s[i].id]+=2; //自身和最后一步
    }
    for (int i=1;i<=n;i++) printf("%d ",ans[i]);
    return 0;
}