初看这道题,秒想到区间覆盖。

但又看到要求钦定,只想到钦定之后下一个一定是合法最远的,苦思冥想想不出什么好的算法。

无奈点开题解,发现只差了一步,只需要单调队列+倍增跳就好了,是我蠢了。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
#define eps 1e-8
using namespace std;
const int N=2e5+5,mod=20170408;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct node{ll l,r;int id;bool operator <(const node a)const{return l<a.l;}}a[N<<1];
int q[N<<1],f[N<<1][20],ans[N<<1];
int main()
{
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)
    {
        qr(a[i].l),qr(a[i].r);a[i].id=i;
        if(a[i].r<a[i].l)a[i].r+=m;
        a[i+n].l=a[i].l+m,a[i+n].r=a[i].r+m;
    }
    sort(a+1,a+(n<<1)+1);
    int l=1,r=1;q[1]=n<<1;f[n<<1][0]=n<<1;
    for(int i=(n<<1)-1;i;i--)
    {
        while(l<=r&&a[q[l]].l>a[i].r)++l;
        f[i][0]=q[l];//其实省略了一步,但不影响。 
        q[++r]=i;
    }
    for(int i=1;i<=19;i++)
        for(int x=1;x<=(n<<1);x++)
            f[x][i]=f[f[x][i-1]][i-1];
    for(int i=1;i<=n;i++)
    {
        int id=a[i].id,x=i;
        for(int j=19;~j;j--)
            if(a[f[x][j]].r-a[i].l<m)x=f[x][j],ans[id]|=1<<j;
        ans[id]+=2;
    }
    for(int i=1;i<=n;i++)qw(ans[i]),putchar(' ');
    return 0;
}