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

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct node
{
	int idx, l, r;
};
vector<node> a;
int n, m, st[444444][20];
vector<int> ans;
bool cmp(node a, node b)
{
	return a.l < b.l;
}
signed main()
{
    freopen("flagplan.in", "r", stdin);
    freopen("flagplan.out", "w", stdout);
	cin >> n >> m;
	a.resize(n);
	ans.resize(n * 2);
	memset(st, -1, sizeof(st));
	for (int i = 0; i < n; i++) { 
        cin >> a[i].l >> a[i].r;
		if (a[i].r < a[i].l) {
            a[i].r += m;
        }
        a[i].idx = i;
	}
	sort(a.begin(), a.end(), cmp); 
    a.resize(n * 2);
	for (int i = 0; i < n; i++)  {
		a[i + n].idx = a[i].idx;
        a[i + n].l = a[i].l + m;
        a[i + n].r = a[i].r + m;
    }
	for (int i = 0, cnt = i; i < (n << 1); i++) { 
		while (cnt < (n << 1) && a[cnt].l <= a[i].r) { 
			cnt++;
        }
		st[i][0] = cnt - 1;
	}
	for (int i = 1; i < 20; i++) {
		for (int j = 0; j < (n << 1); j++) { 
			if (st[j][i - 1] != -1) {
				st[j][i] = st[st[j][i - 1]][i - 1];
            }
        }
    }
	for (int i = 0; i < n; i++) { 
        int pos = i, tp = a[pos].l + m, cnt = 0;
	    for (int j = 19; j >= 0; j--) {
		    if (a[st[pos][j]].r < tp && st[pos][j] != -1) {
    			cnt += (1 << j);
                pos = st[pos][j];
            }
    	}
    	ans[a[i].idx] = cnt + 2;
    }
	for (int i = 0; i < n; i++) { 
		cout << ans[i] << ' ';
    }
	return 0;
}