记录编号	606673	评测结果	RRRRRRRRRR
题目名称	1438.[NOIP 2013]火柴排队	最终得分	0
用户昵称	彭欣越	是否通过	未通过
代码语言	C++	运行时间	0.029 s
提交时间	2025-10-01 17:25:14	内存使用	4.03 MiB

#include <bits/stdc++.h>
#define debug cout << "qwq" <<endl
using namespace std;
typedef long long ll;
const int N=200010;
ll n,m,f[N*2][22],ans[N];
struct node {
	ll l,r;
	int id;
}a[N*2];
bool cmp (node x,node y) {
	if (x.l==y.l) return x.r<y.r;
	return x.l<y.l;
}
ll query (int idx,int k) {
	int t=idx;
	for (int i=20;i>=0;i--) {
		if ((k>>i)&1) t=f[t][i];
	} 
	return a[t].r-a[idx].l;
}
int main() {
	freopen(".in","r",stdin);
	freopen(".out","w",stdout); 
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    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].l+m,a[i].r+m,a[i].id};
	for (int i=1;i<=n*2;i++) {
		int l=i,r=n*2;
		while (l<r) {
			//debug;
			int mid=(l+r+1)/2;
			if (a[mid].l<=a[i].r&&a[i].r<=a[mid].r) l=mid;
			else r=mid-1;
		}
		f[i][0]=l;
	}
	for (int j=1;j<=20;j++) {
		for (int i=1;i<=n*2;i++) {
			f[i][j]=f[f[i][j-1]][j-1];
		}
	}
	for (int i=1;i<=n;i++) {
		int l=0,r=n-1;
		while (l<r) {
			int mid=(l+r)/2;
			if (query(i,mid)>=m) r=mid;
			else l=mid+1;
		}
		ans[a[i].id]=l+1;
	}
	for (int i=1;i<=n;i++) cout << ans[i] <<' ';
    return 0;
}