Node w[400010]; int jump[400010][20]; int ans[200010]; int n, m;
boolcmp(const Node& a, const Node& b) { return a.l < b.l; }
voidpre() { int nxt = 1; for (int i = 1; i <= n * 2; i++) { //由于已经按照左端点排序并且保证区间不重合,此处不需要将 nxt 重设为 1 while (nxt <= n * 2 && w[nxt].l <= w[i].r) { nxt++; } jump[i][0] = nxt - 1; } for (int i = 1; (1 << i) <= n; i++) { for (int s = n * 2; s >= 1; s--) { // s 循环的正反无所谓,因为使用的是跳了一半的数据,与此层 s 无关 jump[s][i] = jump[jump[s][i - 1]][i - 1]; } } }
intquery(int x) { int end = w[x].l + m;// 这一圈的结束,下一圈的开始 int cur = x; int ans = 0;
for (int i = log2(n); i >= 0; i--) {// 2^i 代表一次跳几个边防站 int pos = jump[cur][i]; if (w[pos].r < end) {//判断是否完成覆盖 if (pos) { ans += 1 << i; cur = pos; } } else break; if (pos && w[pos].r < end) { ans += 1 << i; cur = pos; } } // ans 倍增过程中跳过的线段,要想圆满覆盖还要加上自己本身和最后一根线段 return ans + 2; }
intmain() { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> w[i].l >> w[i].r; w[i].id = i; if (w[i].r < w[i].l) w[i].r += m; } sort(w + 1, w + n + 1, cmp); //按照左端点排序以便贪心 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; } pre(); for (int i = 1; i <= n; i++) { ans[w[i].id] = query(i); } for (int i = 1; i <= n; i++) { cout << ans[i] << " "; } return0; }