首先题目给的限制条件很奇怪，下标差 \(K\) 而值域差 \(1\)。我们变成逆排列，然后就转换成了下标差 \(1\)，值域差 \(K\) 了，每次操作就相当于交换相邻的两个差 \(\ge K\) 的数。
假设新的逆排列为 \(Q_i\)。我们发现，假如存在两个数差 \(<K\)，那么它们的相对位置关系一定不变。那么我们现在有若干个限制 \((i, j)\)，满足 \(Q_i\) 一定在 \(Q_j\) 前。那么我们可以将这个限制建出一个图，然后跑拓扑排序，便得到了一个可能的 \(Q_i\) 序列。
我们要求 \(P_i\) 字典序最小，这意味着 \(Q_i\) 中较小的数要尽可能靠前。那么最后一个数肯定尽可能大，让较小的数靠前。那么我们实际上就是要求 \(Q_i\) 翻转过来的字典序最大。那么我们只需要建反图，然后跑拓扑排序，每次选编号最大的点即可。
但是边数很多，直接跑显然不可行。我们可以拿线段树维护每个点的度数，然后维护一个最小值，每次删去一个数 \(i\)，入度会减少 \(1\) 的点的区间为 \((i - K, i + K)\)，然后找入度为 \(0\) 的点即可。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int n, k, p[MAXN], q[MAXN];
struct SegmentTree {
struct Node {
pair<int, int> mn;
int tag;
} t[MAXN << 2];
#define lc (i << 1)
#define rc (i << 1 | 1)
void pushDown(int i) {
if (t[i].tag) {
t[lc].mn.first += t[i].tag, t[lc].tag += t[i].tag;
t[rc].mn.first += t[i].tag, t[rc].tag += t[i].tag;
t[i].tag = 0;
}
}
void build(int i = 1, int l = 1, int r = n) {
t[i].mn = { 0, l };
if (l == r) return;
int mid = (l + r) >> 1;
build(lc, l, mid), build(rc, mid + 1, r);
}
void update(int d, int v, int i = 1, int l = 1, int r = n) {
if (l == r) {
t[i].mn.first = v;
return;
}
int mid = (l + r) >> 1;
pushDown(i);
if (d <= mid) update(d, v, lc, l, mid);
else update(d, v, rc, mid + 1, r);
t[i].mn = min(t[lc].mn, t[rc].mn);
}
void add(int a, int b, int v, int i = 1, int l = 1, int r = n) {
if (a <= l && r <= b) {
t[i].mn.first += v, t[i].tag += v;
return;
}
int mid = (l + r) >> 1;
pushDown(i);
if (a <= mid) add(a, b, v, lc, l, mid);
if (b > mid) add(a, b, v, rc, mid + 1, r);
t[i].mn = min(t[lc].mn, t[rc].mn);
}
} st;
struct BinaryIndexTree {
int a[MAXN];
#define lowbit(x) (x & (-x))
void add(int d, int v) {
while (d <= n) {
a[d] += v;
d += lowbit(d);
}
}
int query(int d) {
if (!d) return 0;
int ans = 0;
while (d) {
ans += a[d];
d -= lowbit(d);
}
return ans;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
} bit;
int ans[MAXN], m;
int ans2[MAXN];
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) {
scanf("%d", &p[i]);
q[p[i]] = i;
}
st.build();
priority_queue<int> que;
for (int i = n; i >= 1; i--) {
int ind = bit.query(max(q[i] - k + 1, 1), min(q[i] + k - 1, n));
if (!ind) {
que.push(q[i]);
st.update(q[i], INT_MAX);
} else {
st.update(q[i], ind);
}
bit.add(q[i], 1);
}
while (!que.empty()) {
int u = que.top(); que.pop();
ans[++m] = u;
st.add(max(1, u - k + 1), min(u + k - 1, n), -1);
while (st.t[1].mn.first == 0) {
int v = st.t[1].mn.second;
que.push(v);
st.update(v, INT_MAX);
}
}
for (int i = 1; i <= n; i++) {
ans2[ans[n - i + 1]] = i;
}
for (int i = 1; i <= n; i++) {
printf("%d\n", ans2[i]);
}
return 0;
}