考虑转化对所有能操作得到的\(P\)集合的判定。
求\(P\)的逆置换\(Q\)（交换下标和值），操作转化为：若\(|Q_i-Q_{i+1}|\ge K\)，可交换\(i\)和\(i+1\)。
这样转化交换的就是相邻两个位置的值，如果没有前面的限制，任何排列都可以被操作得到。
加上限制，显然有必要条件：数值对\((u,v)\)的位置大小关系不变。实际上这个条件是充分的，任何满足该条件的排列都可以通过从前往后依次交换到对应位置。
这种交换相邻两个值的操作，能构造出的排列很广阔，这也是转化成\(Q\)的意义。
换回\(P\)判定条件变为了：不改变所有\(|i-j|<K\)的\(P_i\)和\(P_j\)的大小关系。
即若干个不等式限制。考虑拓扑序的最小字典序。
字典序最小等价于优先最大的值填入尽量靠后的位置。
这里值大连小。从大到小考虑每个值填的位置，每次填入存入度为\(0\)位置的优先队列里最大的即可。
不过连边是\(O(nk)\)。
入度为\(0\)相当于是\((x-k,x+k)\)里的最大值。线段树维护最大值，一开始扫一遍把入度为\(0\)的加入。
每次填了的位置断边，就在线段树上把这个值赋为\(-inf\)，然后分别判\((x-k,x)\)和\((x,x+k)\)中的最大值所在位置的入度是否为\(0\)。
点击查看代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
const int inf = 1e9;
struct seg {int l, r, mx;} T[N << 2];
priority_queue<int> Q;
int n, K, p[N], q[N], ans[N];
void P_up(int x) {T[x].mx = max(T[x << 1].mx, T[x << 1 | 1].mx);}
void Build(int x, int l, int r) {
T[x].l = l; T[x].r = r;
if(l == r) {T[x].mx = p[l]; return;}
int mid = (l + r) >> 1;
Build(x << 1, l, mid); Build(x << 1 | 1, mid + 1, r);
P_up(x);
}
void Update(int x, int p) {
if(T[x].l == T[x].r) {T[x].mx = -inf; return;}
int mid = (T[x].l + T[x].r) >> 1;
(p <= mid) ? Update(x << 1, p) : Update(x << 1 | 1, p);
P_up(x);
}
int Mx(int x, int l, int r) {
if(l > r) return -inf;
if(l <= T[x].l && T[x].r <= r) {return T[x].mx;}
int mid = (T[x].l + T[x].r) >> 1, mx = -inf;
if(l <= mid) mx = Mx(x << 1, l, r);
if(r > mid) mx = max(mx, Mx(x << 1 | 1, l, r));
return mx;
}
bool Ins[N];
void check(int u) {
if(Ins[u]) return;
if(Mx(1, max(1, u - K + 1), min(n, u + K - 1)) != p[u]) return;
Ins[u] = 1; Q.push(u);
}
int main() {
scanf("%d%d", &n, &K);
for(int i = 1; i <= n; i++) {scanf("%d", &p[i]); q[p[i]] = i;}
Build(1, 1, n);
for(int i = 1; i <= n; i++) {check(i);}
int v = n;
while(!Q.empty()) {
int x = Q.top(); Q.pop();
ans[x] = v--; Update(1, x);
int wl = Mx(1, max(1, x - K + 1), x - 1), wr = Mx(1, x + 1, min(n, x + K - 1));
if(wl > -inf) {check(q[wl]);}
if(wr > -inf) {check(q[wr]);}
}
for(int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}