首先显然要先把原数组重新映射一下，令映射过后的数组为 $a_i$

因为题目要求 $|a_j - a_i| >= K$ 的可以置换，那么反之，则有 $|a_j - a_i| < K$ 的 $i, j$ 相对位置不变

故最简单的方法就是对于每个 $i$，将其与所有满足 $|a_j - a_i| < K$ 的 $j$ 连边，然后跑一边拓扑，复杂度 $O (n^2)$

然后考虑在 $a_i$ 连的这么多边中，若是存在边 $(i, j), (j, k), (i, k)$，其中 $i < j < k$，那么显然 $(i, k)$ 的存在性是无关紧要的

又 $a_i$ 可连边的权值范围是 $(a_i - K, a_i) \cup (a_i, a_i + K)$，那么只需要分别向两个区间中标号最小的那个点连边就好了（单向边，并且一定向标号比自己大的点连），这样就相当于是将原来的乱七八糟连接的图变成了一条条单向的链，并且这些链可以覆盖原来的所有情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

#define lson root << 1
#define rson root << 1 | 1

using namespace std;

const int MAXN = 5e05 + 10;
const int MAXM = 5e05 + 10;

const int INF = 0x7fffffff;

struct LinkedForwardStar {
	int to;

	int next;
} ;

LinkedForwardStar Link[MAXM << 1];
int Head[MAXN]= {0};
int size = 0;

void Insert (int u, int v) {
	Link[++ size].to = v;
	Link[size].next = Head[u];

	Head[u] = size;
}

int N, K;
int a[MAXN]= {0}, b[MAXN]= {0};

int minv[MAXN << 2];
void modify (int root, int left, int right, int posi, int value) {
	if (left == right) {
		minv[root] = value;
		return ;
	}
	int mid = (left + right) >> 1;
	if (posi <= mid) modify (lson, left, mid, posi, value);
	else modify (rson, mid + 1, right, posi, value);
	minv[root] = min (minv[lson], minv[rson]);
}
int query (int root, int left, int right, int L, int R) {
	if (L > R) return INF;
	if (L <= left && right <= R)
		return minv[root];
	int mid = (left + right) >> 1;
	int mv = INF;
	if (L <= mid) mv = min (mv, query (lson, left, mid, L, R));
	if (R > mid) mv = min (mv, query (rson, mid + 1, right, L, R));
	return mv;
}

int indeg[MAXN]= {0};
priority_queue<int, vector<int>, greater<int> > que;
int ret[MAXN]= {0}, rcnt = 0;
void topo () {
	for (int i = 1; i <= N; i ++)
		if (! indeg[i])
			que.push(i);
	while (! que.empty()) {
		int p = que.top();
		que.pop();
		ret[p] = ++ rcnt;
		for (int i = Head[p]; i; i = Link[i].next) {
			int v = Link[i].to;
			indeg[v] --;
			if (! indeg[v]) que.push(v);
		}
	}
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}

int main () {
	N = getnum (), K = getnum ();
	for (int i = 1; i <= N; i ++)
		a[i] = getnum ();
	for (int i = 1; i <= N; i ++)
		b[a[i]] = i;
	memset (minv, 0x3f, sizeof (minv));
	for (int i = N; i >= 1; i --) {
		int p1 = query (1, 1, N, max (1, b[i] - K + 1), b[i] - 1);
		int p2 = query (1, 1, N, b[i] + 1, min (N, b[i] + K - 1));
		if (p1 >= 1 && p1 <= N) Insert (b[i], b[p1]), indeg[b[p1]] ++;
		if (p2 >= 1 && p2 <= N) Insert (b[i], b[p2]), indeg[b[p2]] ++;
		modify (1, 1, N, b[i], i);
	}
	topo ();
	for (int i = 1; i <= N; i ++)
		printf ("%d\n", ret[i]);

	return 0;
}

/*
4 2
4 2 3 1
*/

/*
5 1
5 4 3 2 1
*/

/*
8 3
4 5 7 8 3 1 2 6
*/