题意

给你一个环，有 个区间,区间之间互相不覆盖。求当任意一个区间必须选择时，最少需要多少个区间能够覆盖整个环。

思路

对于一个战士 ，如果选了他，那么下一个战士 一定是所有左端点小于等于 的右端点的战士中最大的一个战士，因为这样子才是是最优的。所以我们只需要预处理加二分找到下一个战士就好了。然后一个一个的找有点慢，所以就用倍增优化一下就好。

代码

#include<bits/stdc++.h>
#define ll long long
const int N=1e6+5,INF=0x3f3f3f3f,mod=998244353;
using namespace std;

int n,m;
struct node
{
    int l,r,id;
}zs[N];
inline int read()
{
    register int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}

int qpow(int a,int b)
{
    int ans=1;
    while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b>>=1;}
    return ans;
}

int f[N][31],s[N][31],ans[N],p;
bool cmp(node x,node y){return x.l<y.l||(x.l==y.l&&x.r<y.r);}

int find(int x,int l,int r)
{
    int res=p+1,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(zs[mid].l<=x) l=mid+1,res=mid;
        else r=mid-1;
    }
    return res;
}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        zs[i].l=read(),zs[i].r=read(),zs[i].id=i;
    p=n;memset(ans,0,sizeof(ans));
    for(int i=1;i<=n;i++) 
     if(zs[i].l>zs[i].r) zs[i].r+=m;
     else zs[++p].l=zs[i].l+m,zs[p].r=zs[i].r+m,zs[p].id=i;
    sort(zs+1,zs+p+1,cmp);zs[p+1].r=2e9;
    for(int i=0;i<=30;i++) 
     for(int j=1;j<=p+1;j++) 
      f[j][i]=p+1;
    for(int i=1;i<=p;i++) f[i][0]=find(zs[i].r,i+1,p+1);
    for(int j=1;j<=30;j++) 
     for(int i=1;i<=p;i++) 
      f[i][j]=f[f[i][j-1]][j-1];
    for(int i=1;i<=p;i++)
     if(zs[i].id&&!ans[zs[i].id])
     {
        int now=i,to=zs[i].l+m;
        for(int j=30;j>=0;j--) 
         if(zs[f[now][j]].r<to) 
          now=f[now][j],ans[zs[i].id]+=(1<<j);
     }
    for(int i=1;i<=n;i++) printf("%d ",ans[i]+2);
    return 0;
}

最后答案输出时加2是因为没有计算第一个和最后一个。