P3509. ZAB-Frog

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

考点

双指针
倍增

题解

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 50;
ll n, k, m, a[maxn], nxt[maxn], fa[maxn][62];

void init() {
  // 每个元素的第k远
  int l = 1, r = 1 + k;
  for (int i = 1; i <= n; ++i) {
    while (r + 1 <= n && a[r + 1] - a[i] < a[i] - a[l]) ++l, ++r;
    nxt[i] = a[r] - a[i] > a[i] - a[l] ? r : l;
  }
  // 倍增优化跳链，初始化
  for (int i = 1; i <= n; ++i) fa[i][0] = nxt[i];
  for (int j = 1; j <= 61; ++j) {
    for (int i = 1; i <= n; ++i) {
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
  }
}

int jump(int bg, ll x) {
  for (int i = 61; i >= 0; --i) {
    if (x >= (1ll << i)) {
      bg = fa[bg][i];
      x -= (1ll << i);
    }
  }
  return bg;
}

int main() {
  cin >> n >> k >> m;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  init();
  for (int i = 1; i <= n; ++i) cout << jump(i, m) << " ";
  return 0;
}