AtCoder

Luogu

分析

令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小，则应使 $a$ 的字典序尽量小。

那么题目变为：给定排列 $a_{1..n}$，如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$，求可能排列中字典序最小的。

注意到如果 $a_i,a_j$ 不可能发生交换（也就是说 $|a_i-a_j|<k$），那么两者的相对顺序不会改变。于是对于每一对不可能发生交换的 $a_i,a_j$ ，假设 $i<j$，则连一条 $i\to j$ 的有向边。那么字典序最小的拓扑序就是字典序最小的 $a$ 了，再还原回去即可得到答案。

现在的主要问题在于边数是 $O(n^2)$ 级别的，考虑优化。

考虑到如果 $i<j<k$ ，且有三条边 $i\to j,i\to k,j\to k$，那么 $i\to k$ 这条边是可以去掉的。

那么对于每个 $a_i$，只需要找到两个分别 $<a_i,>a_i$ 的 $j$，满足 $|a_i-a_j|<k$ 且尽量小，然后 $a_i$ 向 $a_j$ 连边即可。

具体的，倒序扫描所有 $a_i$，每次在线段树中求区间最小值，然后把 $a_i$ 位置修改为 $i$。

这个正确性的话可以感性理解一下...？

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;
const int inf=0x3f3f3f3f;

int n,k,a[N];

#define ls (o<<1)
#define rs (o<<1|1)
int minv[N<<2];
inline void pushup(int o) { minv[o]=min(minv[ls],minv[rs]); }
inline void modify(int o,int l,int r,int p,int w) {
    if (l==r) { minv[o]=w; return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
inline int query(int o,int l,int r,int ql,int qr) {
    if (ql>qr) return inf;
    if (ql<=l&&r<=qr) return minv[o];
    int mid=(l+r)>>1,res=inf;
    if (ql<=mid) res=min(res,query(ls,l,mid,ql,qr));
    if (qr>mid) res=min(res,query(rs,mid+1,r,ql,qr));
    return res;
}
#undef ls
#undef rs

struct edge { int v,nxt; } e[N<<1];
int head[N],deg[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

priority_queue<int,vector<int>,greater<int> > Q;
int ans[N],tim=0;
inline void topsort() {
    for (re int i=1;i<=n;++i) if (!deg[i]) Q.push(i);
    while (!Q.empty()) {
        int u=Q.top(); Q.pop(); ans[u]=++tim;
        for (re int i=head[u];i;i=e[i].nxt) {
            int v=e[i].v; --deg[v];
            if (!deg[v]) Q.push(v);
        }
    }
}

int main() {
    n=read(),k=read();
    for (re int i=1;i<=n;++i) a[read()]=i;
    memset(minv,0x3f,sizeof(minv));
    for (re int i=n;i;--i) {
        int x=query(1,1,n,a[i]+1,min(a[i]+k-1,n));
        if (x<=n) addEdge(a[i],a[x]),++deg[a[x]];
        int y=query(1,1,n,max(1,a[i]-k+1),a[i]-1);
        if (y<=n) addEdge(a[i],a[y]),++deg[a[y]];
        modify(1,1,n,a[i],i);
    }
    topsort();
    for (re int i=1;i<=n;++i) printf("%d\n",ans[i]);
    return 0;
}