记录编号	606680	评测结果	AAAAAAAAAA
题目名称	3842.[SCOI 2015] 国旗计划	最终得分	100
用户昵称	秋_Water	是否通过	通过
代码语言	C++	运行时间	1.988 s
提交时间	2025-10-01 21:05:41	内存使用	25.17 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct node{
	int l,r,id;
}a[N];
bool cmp(node a,node b){
	return a.l<b.l;
}
int f[2*N][24],ans[2*N],n,m; 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i].l>>a[i].r;
		if(a[i].l>a[i].r){
			a[i].r+=m;
		}
		a[i].id=i;
	}
	sort(a+1,a+n+1,cmp); 
	for(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;
	} 	
	for(int i=1,j=i;i<=2*n;i++){
		while(j<=2*n&&a[j].l<=a[i].r){
			j++;
		}
		j--;
		f[i][0]=j;
	}
	for(int j=1;j<=23;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 ii=i,cnt=0,r=a[i].l+m;
		for(int j=23;j>=0;j--){
			if(f[ii][j]!=0&&a[f[ii][j]].r<r){
				cnt+=(1<<j);
				ii=f[ii][j]; 
			} 
		} 
		ans[a[i].id]=cnt+2; 
	} 
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	} 

	return 0;
}