题意
给出一个元素集合为({1,2,dots,N}) ((1leq Nleq 500,000))的排列(P)，当有(i,j) ((1leq i<jleq N))满足(j-igeq K) ((1leq Kleq N-1))且(|P_{i}-P_{j}|==1)时，可以交换(P_{i})和(P_{j})
求：可能排列中字典序最小的排列
(2 leq N leq 500,000)
题解
看到(|P_i - P_j| = 1)这种东东考虑先搞一个新排列(Q_{P_i} = i)， 可以发现， 如果(Q)的字典序最小， 那么(P)的字典序最小。
考虑一下我们的条件变成了什么， 就是相邻的位置的绝对值大于等于(K)时候，我们可以交换这两个位置上的数。
推广一下限制， 也就是说(i < j, |Q_i - Q_j| <K)的时候需要连一条边((Q_i ightarrow Q_j))表示 (Q_i)必须在(Q_j)以前出现。
那么这样会搞出(n^2)条边来， 然后剩下的就是菜肴制作那个题了。
然后考虑优化， 可以发现我们拓扑排序只需要知道一个点是否有入度。把边反向以后， 使用一个值域线段树维护，每次在([x - K + 1, x + K - 1])中查最小值/最大值是否小于当前点(x)， 然后跑拓扑就是了。
还有一个做法是考虑优化连边主要是写起来难受。显然关系有传递性的， 所以找到满足条件的离(i)最靠近的点连边即可。
这里是后面一个的代码。
/*
QiuQiu /qq
____ _ _ __
/ __ (_) | | / /
| | | | _ _ _ | | _ _ / / __ _ __ _
| | | | | | | | | | | | | | | | / / / _` | / _` |
| |__| | | | | |_| | | | | |_| | / / | (_| | | (_| |
\___\_ |_| \__,_| |_| \__, | /_/ \__, | \__, |
__/ | | | | |
|___/ |_| |_|
*/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
namespace Mod {
const int P = 998244353;
inline int mod(int x) { return x + ((x >> 31) & P); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline void dec(int &x, int y) { x = mod(x - y); }
inline int power(int x, int k) {
int res = 1;
while(k) { if(k & 1) res = 1ll * res * x % P; x = 1ll * x * x % P; k >>= 1; } return res;
}
const int inv2 = power(2, P - 2);
}
const int N = 5e5 + 5;
const int INF = 0x3f3f3f3f;
int n, K;
int Q[N], P[N];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
int mx[N << 2];
int qry(int x, int l, int r, int L, int R) {
if(L <= l && r <= R) return mx[x];
int mid = (l + r) >> 1;
if(R <= mid) return qry(ls(x), l, mid, L, R);
if(L > mid) return qry(rs(x), mid + 1, r, L, R);
return max(qry(ls(x), l, mid, L, R), qry(rs(x), mid + 1, r, L, R));
}
void mdf(int x, int l, int r, int p, int v) {
if(l == r) { mx[x] = v; return ; }
int mid = (l + r) >> 1;
if(p <= mid) mdf(ls(x), l, mid, p, v);
else mdf(rs(x), mid + 1, r, p, v);
mx[x] = max(mx[ls(x)], mx[rs(x)]);
}
vector<int> e[N];
int out[N], deg[N];
int main() {
ios :: sync_with_stdio(false);
cin >> n >> K;
for(int i = 1; i <= n; i ++) {
cin >> P[i]; Q[P[i]] = i;
}
// for(int i = 1; i <= n; i ++) cerr << Q[i] << ' ' ;
for(int i = 1; i <= n; i ++) {
int k = qry(1, 1, n, max(1, Q[i] - K + 1), Q[i]);
if(k) e[Q[i]].push_back(Q[k]), deg[Q[k]] ++;
k = qry(1, 1, n, Q[i], min(Q[i] + K - 1, n));
if(k) e[Q[i]].push_back(Q[k]), deg[Q[k]] ++;
mdf(1, 1, n, Q[i], i);
//cout << k << endl;
}
priority_queue<int> q;
for(int i = 1; i <= n; i ++) if(! deg[i]) {
q.push(i);
// cerr << i << endl;
}
int tac = n;
while(q.size()) {
int x = q.top(); q.pop();
//cerr << x << ' ' << out[x] << endl;
out[x] = tac --; //tac --;
for(int y : e[x]) {
deg[y] --;
if(deg[y] == 0) q.push(y);
}
}
for(int i = 1; i <= n; i ++) cout << out[i] << endl;
return 0;
}