求调

#include <bits/stdc++.h>

using namespace std;

const int N = 4e5+5;
const int M = 1e9+5;
int n, m;

struct warrior{
	int id;
	int l;
	int r;
	inline bool operator<(const warrior w) const{
		return l < w.l;
	}
	
	inline bool operator>(const warrior w) const{
		return l > w.l;
	}
}w[N*2];

int jump[N*2][20];

inline int getNextWarrior(int id){
	int r;
	warrior wa = w[id];
	for (r=id; r<=2*n; r++){
		if (w[r].l>wa.r) break;
	}
	return r-1;
}

inline void initJump(){
	for (int i=1; i<=2*n; i++){
		jump[i][0] = getNextWarrior(i);
	}
}

inline void calcJump(){
	for (int i=1; (1<<i)<=n; i++){
		for (int s=1; s<=2*n; s++){
			jump[s][i] = jump[jump[s][i-1]][i-1];
		}
	}
}

int wr[N];
inline void calc(int n){
	int dest = w[n].l + m;
	int cur = n;
	int ws=1;
	for (int i=log2(N); i>=0; i--){
		int pos = jump[cur][i];
		if (pos && w[pos].r < dest){
			ws += 1<<i;
			cur = pos;
		}
	}
	wr[w[n].id] = ++ws;
}

int main(){
	scanf("%d %d", &n, &m);
	for (int i=1; i<=n; i++){
		w[i].id=i;
		scanf("%d %d", &w[i].l, &w[i].r);
		if (w[i].l > w[i].r){
			w[i].r += m;
		}
	}
	sort(w+1, w+n+1);
	
	for (int i=1; i<=n; i++){
		w[n+i].id=w[i].id;
		w[n+i].l=w[i].l+m;
		w[n+i].r=w[i].r+m;
	}
	
	initJump();
	calcJump();
	
	for (int i=1; i<=n; i++) calc(i);
	for (int i=1; i<=n; i++) printf("%d ", wr[i]);
	return 0;
}