发现 的数无法交换，于是这两个数的相对位置是固定的。换言之，不妨设 ，那么 始终会在 前面。对于所有这样的 ，我们将 连一条有向边到，按照题目要求做拓扑排序即可。
如何做？正常最小拓扑序是把所有入度为 0 的点放入优先队列中，然后每次取堆顶的点并将其连出的边删除。时间复杂度为 ，瓶颈为图中可能的边数。
思考一下如何优化，首先可以对原数组离散化，用一个线段树来维护当前可能的最小位置，每次取出作为答案并更新与其有连边的点的入度即可。具体地，若当前点的权值为 u ，则 \ 中的所有权值对应的点的入度 −1 。需要一个带懒标记线段树做区间更新。
时间复杂度：
#include <bits/stdc++.h>
#define rep(i, a, b) for (int i = (a); i <= (b); ++i)
#define per(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define vi vector<int>
#define fi first
#define se second
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define sz(x) int(x.size())
#define ll long long
using namespace std;
inline ll read() {
ll x = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - 48;
ch = getchar();
}
return x * f;
}
const int N = 2e5 + 5;
int n, K, a[N], val[N], deg[N];
unordered_map<int, int> vis;
#define ls (p << 1)
#define rs (ls | 1)
#define mid ((L + R) >> 1)
pii t[N << 2];
int tag[N << 2];
inline pii Min(const pii a, const pii b) {
if (a.se == b.se)
return make_pair(min(a.fi, b.fi), a.se);
return a.se < b.se ? a : b;
}
void build(int p, int L, int R) {
if (L == R) {
t[p] = make_pair(L, deg[L]);
return;
}
build(ls, L, mid), build(rs, mid + 1, R);
t[p] = Min(t[ls], t[rs]);
}
void push(int p, int v) { tag[p] += v, t[p].se += v; }
void down(int p) {
if (!tag[p])
return;
push(ls, tag[p]), push(rs, tag[p]);
tag[p] = 0;
}
void upd(int p, int L, int R, int l, int r, int v) {
if (l > R || r < L)
return;
if (l <= L && R <= r) {
push(p, v);
return;
}
down(p);
upd(ls, L, mid, l, r, v), upd(rs, mid + 1, R, l, r, v);
t[p] = Min(t[ls], t[rs]);
}
int T[N];
void add(int x) {
for (; x <= n; x += x & -x) T[x]++;
}
int Q(int x) {
int res = 0;
for (; x; x -= x & -x) res += T[x];
return res;
}
int main() {
n = read(), K = read();
rep(i, 1, n) a[i] = read(), val[i] = a[i];
sort(val + 1, val + n + 1);
rep(i, 1, n) {
vis[a[i]]++;
a[i] = lower_bound(val + 1, val + n + 1, a[i]) - val + vis[a[i]] - 1;
}
// calculating in-degree
rep(i, 1, n) {
int x = lower_bound(val + 1, val + n + 1, val[a[i]] - K) - val - 1;
int y = lower_bound(val + 1, val + n + 1, val[a[i]] + K + 1) - val - 1;
deg[a[i]] = (i - 1) + Q(x) - Q(y);
add(a[i]);
}
build(1, 1, n);
rep(i, 1, n) {
int u = t[1].fi;
cout << val[u] << '\n';
int x = lower_bound(val + 1, val + n + 1, val[u] - K) - val - 1;
// cout << 1 << ' ' << x << '\n';
int y = lower_bound(val + 1, val + n + 1, val[u] + K + 1) - val - 1;
// cout << y+1 << ' ' << n << '\n';
// cout << u << ' ' << u << '\n';
upd(1, 1, n, 1, x, -1);
upd(1, 1, n, y + 1, n, -1);
upd(1, 1, n, u, u, n);
}
return 0;
}