题目链接

牛客（无数据规模）：https://ac.nowcoder.com/acm/problem/20302
洛谷（有数据规模）：https://www.luogu.com.cn/problem/P4155
数据规模：
图片说明

解题思路

贪心+倍增；
好难讲，直接讲代码吧。
f数组就是倍增数组，f[i][j]表示编号为i的战士，尽量优地选其身后的1<<j个战士能奔袭的最远，最后那个战士的编号就是f[i][j]。不是很好理解，往后看看应该可以明白
f[i][0]的赋值通过贪心，类似于区间覆盖问题，每次选“左端点”小于“编号为i的战士的左端点”的战士，f[i][0]存被选战士的编号。
f[i][j]的赋值就正常折半跳，进行赋值。

大致思路：
破链成环，具体看代码吧。
画个图会好理解一点。
循环枚举每个区间作为起点，每次倍增跳，找到能覆盖整个区间的战士序号，在倍增的过程中对个数进行累加（通过移位操作）。

AC代码

#include<bits/stdc++.h>
using namespace std;

const int N=5e5+100;//多开点 

struct soldier{int l,r,idx;}a[N];

int n,m,f[N][20],lg[N],ans[N];

inline int read(){int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch-'0');return x*f;}
inline void getlg(){for(int i=1;i<=n;i++)lg[i]=lg[i-1]+(1<<lg[i-1]==i);}

inline void getf()//对f数组赋值 
{
    //int mx=0,pos=1;//对应下面的标准代码 
    for(int i=1,j=1;i<=2*n;i++)//贪心 
    {
        while(j<=2*n && a[j].l<=a[i].r) j++;
        //if(a[j].r>mx) mx=a[j].r,pos=j,j++;//这是比较标准的代码，找到右端点最大的区间序号。但是因为题目中要求任意区间不包含，所以排完序后只要找到满足要求的最大右端点就是f[i][0]的值。 
        f[i][0]=j;
        //f[i][0]=pos;//标准代码 
    }
    for(int j=1;j<=lg[n];j++)//对f的全部赋值 
    for(int i=1;i<=2*n;i++)
    f[i][j]=f[f[i][j-1]][j-1];
}
bool cmp(soldier t1,soldier t2){return t1.l<t2.l;}

int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        int l=read(),r=read();
        if(l>r)//右端点小于左端点 
        {
            a[i].l=l;    a[i].r=r+m;    a[i].idx=i;//左端点不变右端点加m
            a[i+n].l=l+m;a[i+n].r=r+m+m;a[i+n].idx=i;//左端点加m，右端点加2m
        }
        else 
        {
            a[i].l=l;    a[i].r=r;      a[i].idx=i;//左右端点不变
            a[i+n].l=l+m;a[i+n].r=r+m;a[i+n].idx=i;//左右端点都加m
        }
    }

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

    getlg();//移位的个数 
    getf();

    for(int i=1;i<=n;i++)
    {
        int l=a[i].l,sum=1,pos=i;//sum初始化为1，表示包含自身这段区间 
        for(int j=lg[n];j>=0;j--)
        {
            if(a[f[pos][j]].r-l>=m) continue;//覆盖的区间长度大于等于m了 
            pos=f[pos][j];sum+=(1<<j);
        }
        ans[a[i].idx]=sum+1;//加上最后一个刚好覆盖超过m的区间 
    }

    for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
    return 0;
}

总结

看了大佬的思路后自己实现的时候，一直wa90，裂开，对拍也拍不出来，因为数据的要求条件有点多。
最后发现是自己的存储上，少了 a[i+n].l=l+m;a[i+n].r=r+m+m;a[i+n].idx=i;，当时以为超界了，没必要存了，后来一想确实要存，确实有情况可能选到这个区间。