\(n\) 个草垛排成一排，第 \(i\) 个的高度为 \(h_i\)，两个草垛 \(i, j\) 之间能够交换当且仅当 \(|h_i - h_j| \le k\)，求交换任意次后字典序最小的草垛排列。
\(n, k \le 10^5, h_i \le 10 ^ 9\)。

一道古老的湖北省内测试题。

我们注意到对于任意 \(i, j\)，如果 \(|h_i - h_j| > k\) 的话，那么 \(i, j\) 的相对次序是不会改变的，那么一个很好想的暴力就是找出所有满足 \(i < j, |h_i - h_j| > k\) 的 \(i, j\)，然后在 \(i, j\) 间连边表示拓扑顺序，然后用一个优先队列来维护拓扑排序即可构造出字典序最小的序列。时间复杂度为 \(\mathcal{O}(n^2 \log n)\)，可以拿 \(30\) 分。

考虑正解。从左向右遍历每一个草垛，假设当前已经到了第 \(i\) 个草垛，且前边的 \(i - 1\) 个草垛已经是字典序最小的了。我们考虑将 \(i\) 插到哪里会使字典序最小。一个很显然的事实是，草垛 \(i\) 能插入的位置 \(j\) 一定满足对于任意的 \(j \le l < i\)，都有 \(|h_i - h_l| \le k\)。那么首先要找到一个最小的 \(j\)，样 \(i\) 就只能插入到 \([j, i)\) 中。

再考虑插到哪里会让字典序变小。贪心地，我们找到一个最小的 \(p \in [j, i)\) 并且满足 \(h_p > h_i\)，将 \(i\) 插入到 \(p\) 的前边即可。

上述过程不难用 FHQ Treap 实现，具体而言，需要支持按秩合并与分裂，两种平衡树上二分（用于求出 \(j\) 与 \(p\)）即可。总体时间复杂度 \(\mathcal{O}(n \log n)\)。

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e5 + 50;
int n, k, h[N];
template<int N = 300050>
struct FHQTreap {
  std::mt19937 rnd;
  std::random_device rd;
  struct Node {
    int lc = 0, rc = 0;
    int max = 0, min = 0, val = 0, siz = 0, prm;
  } t[N];
  int cnt = 0, rt = 0;
  FHQTreap() { rnd = std::mt19937(rd()), t[rt].min = 2e9, t[rt].max = 0; }
  int &lc(int u) { return t[u].lc; }
  int &rc(int u) { return t[u].rc; }
  void pushup(int u) {
    t[u].siz = t[lc(u)].siz + t[rc(u)].siz + 1;
    t[u].max = std::max({t[u].val, t[lc(u)].max, t[rc(u)].max});
    t[u].min = std::min({t[u].val, t[lc(u)].min, t[rc(u)].min});
  }
  int init(int val) {
    cnt++;
    t[cnt].val = t[cnt].max = t[cnt].min = val;
    t[cnt].prm = rnd(), t[cnt].siz = 1;
    return cnt;
  }
  void split(int u, int val, int &l, int &r) {
    if (!u) return void(l = r = 0);
    if (t[lc(u)].siz < val) l = u, split(rc(u), val - t[lc(u)].siz - 1, rc(u), r);
    else r = u, split(lc(u), val, l, lc(u));
    pushup(u);
  }
  int merge(int l, int r) {
    if (!l || !r) return l + r;
    if (t[l].prm > t[r].prm) return rc(l) = merge(rc(l), r), pushup(l), l;
    else return lc(r) = merge(l, lc(r)), pushup(r), r;
  }
  int find1(int u, int val) {
    int res = 0;
    while (u) {
      if (std::min(t[u].val, t[rc(u)].min) < val - k || 
          std::max(t[u].val, t[rc(u)].max) > val + k) {
        res += t[lc(u)].siz + 1, u = rc(u);
      } else {
        u = lc(u);
      }
    }
    return res;
  }
  int find2(int u, int val) {
    int res = 0;
    while (u) {
      if (std::max(t[u].val, t[lc(u)].max) > val) u = lc(u);
      else res += t[lc(u)].siz + 1, u = rc(u);
    }
    return res;
  }
  void traverse(int u) {
    if (!u) return;
    traverse(lc(u));
    std::cout << t[u].val << "\n";
    traverse(rc(u));
  }
};
FHQTreap fhq;
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::cin >> n >> k;
  for (int i = 1; i <= n; i++) std::cin >> h[i];
  for (int i = 1, l, r, p; i <= n; i++) {
    fhq.split(fhq.rt, fhq.find1(fhq.rt, h[i]), l, r);
    fhq.split(r, fhq.find2(r, h[i]), r, p);
    fhq.rt = fhq.merge(fhq.merge(l, r), fhq.merge(fhq.init(h[i]), p));
  }
  fhq.traverse(fhq.rt);
  return 0;
}