\(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;
}