[P4155][SCOI2015] 国旗计划 (贪心+倍增)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#define ll long long
#define rg register
using namespace std;
const int N = 4e5+10;

inline int read(){
    int ref=0,x=1;char ch=getchar();
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) ref=ref*10+ch-'0',ch=getchar();
    return ref*x;
}

int n,m;
struct node{
    int l,r,id;
}a[N];
int f[N][20],rel[N>>1];

bool cmp(node a,node b){
    return a.l<b.l;
}

void prepare(){
    int limit=2*n;
    for(int i=1,pos=i;i<=limit;++i){//将 pos写在 for循环里会比写在外面更快...=_=
        while(pos<=limit&&a[pos].l<=a[i].r) pos++;
        f[i][0]=pos-1;
    }
    for(rg int j=1;j<20;++j)
    for(rg int i=1;i<=limit;++i) f[i][j]=f[f[i][j-1]][j-1];
}

void deal(int x){
    int end=a[x].l+m,ans=1,fina=x;
    for(rg int i=19;i>=0;i--){
        int pre=f[x][i];
        if(pre!=0&&a[pre].r<end) ans+=(1<<i),x=pre;
    }
    rel[a[fina].id]=ans+1;
}

int main()
{
    n=read(),m=read();
    for(rg int i=1;i<=n;++i){
        a[i].l=read(),a[i].r=read();
        if(a[i].l>a[i].r) a[i].r+=m;
        a[i].id=i;
    }
    sort(a+1,a+n+1,cmp);
    for(rg int i=1;i<=n;++i){
        a[i+n]=a[i];
        a[i+n].l=a[i].l+m;
        a[i+n].r=a[i].r+m;
    }
    prepare();
    for(rg int i=1;i<=n;++i) deal(i);
    for(rg int i=1;i<=n;++i) printf("%d ",rel[i]);
    return 0;
}