记录编号	606648	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	1.199 s
提交时间	2025-10-01 16:32:44	内存使用	22.55 MiB

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

struct node{
    int l,r,id;
}s[410000];

int f[410000][20],ans[410000];
int n,m;

bool cmp(node aa,node bb){
    return aa.l<bb.l;
}

int main(){
//    freopen("in.in","r",stdin);
    freopen("flagplan.in","r",stdin);
    freopen("flagplan.out","w",stdout);
    scanf("%d %d",&n,&m);
    for (int i=1;i<=n;i++){
        scanf("%d %d",&s[i].l,&s[i].r);
        if (s[i].r<s[i].l){
            s[i].r+=m;
        }
        s[i].id=i;
    }
    sort(s+1,s+n+1,cmp);
    for(int i=1;i<=n;i++){
		s[i+n]=s[i];
		s[i+n].l=s[i].l+m;
		s[i+n].r=s[i].r+m;
	}
	for(int i=1,j=i;i<=2*n;i++){
		while(j<=2*n&&s[j].l<=s[i].r){
			j++;
		}
		j--;
		f[i][0]=j;
	}
	for(int j=1;j<20;j++){
		for(int i=1;i<=2*n;i++){
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	for (int i=1;i<=n;i++){
	    int rr=s[i].l+m,tot=1,k=i,ii=i;
	    for(int j=19;j>=0;j--){
		    if(f[ii][j]!=0&&s[f[ii][j]].r<rr){
			    tot+=(1<<j);
			    ii=f[ii][j];
		    }
	    }
	    ans[s[k].id]=tot+1;
    }
    for (int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}