P4155. 国旗计划

发表于 2024-03-16 分类于洛谷阅读次数： Waline：本文字数： 617 阅读时长 ≈ 2 分钟

考点

倍增
贪心

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 50;
ll n1, n2, m, ans[maxn], f[maxn][20];

struct node {
  ll id_, c_, d_;
  bool operator<(node &b) { return c_ < b.c_ || (c_ == b.c_ && d_ < b.d_); }
} s[2 * maxn];

void init() {
  // 断环为链
  for (int i = 1; i <= n1; ++i) {
    if (s[i].d_ < s[i].c_) s[i].d_ += m;
    s[i + n1] = s[i], s[i + n1].c_ += m, s[i + n1].d_ += m;
  }
  n2 = n1 * 2;
  // 求每个元素的下一跳
  sort(s + 1, s + 1 + n2);
  for (int i = 1, j = 1; i <= n2; ++i) {
    while (j <= n2 && s[j].c_ <= s[i].d_) ++j;
    f[i][0] = j - 1;
  }
  // 倍增初始化
  for (int j = 1; (1 << j) <= n1; ++j) {
    for (int i = 1; i <= n2; ++i) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }
}

void work(int x) {
  ll bg = x, ed = s[x].c_ + m, cnt = 1, nxt;
  for (int i = 19; i >= 0; --i) {
    nxt = f[x][i];
    if (nxt && s[nxt].d_ < ed) {
      x = f[x][i];
      cnt += (1 << i);
    }
  }
  ans[s[bg].id_] = cnt + 1;
}

int main() {
  cin >> n1 >> m;
  for (int i = 1; i <= n1; ++i) cin >> s[i].c_ >> s[i].d_, s[i].id_ = i;
  init();
  for (int i = 1; i <= n1; ++i) work(i);
  for (int i = 1; i <= n1; ++i) cout << ans[i] << " ";
  return 0;
}