Description
你有一个长度为n 的排列P 与一个正整数K
你可以进行如下操作若干次使得排列的字典序尽量小
对于两个满足|i-j|>=K 且|Pi-Pj| = 1 的下标i 与j，交换Pi 与Pj
Solution
看到这种有绝对值的题，看那个绝对值不爽，想办法去掉，
设
那么，如果有两个位置i,j，保证
那么，就每个点往全局所有差值与它小于K的连边，跑一遍拓扑图，
因为现在我们的任务也是要这个序列尽量的小，那么我们就先求出这个序列，再转回答案序列，
每次就找到全局最小的数，保证它入度为0，即这个点已经没有什么点必须在它前面了，那么当前位置就选它，再把它连出的边全部删掉，
这样的复杂度是:
优化
我们发现，其实只要连2条边即可，连向它右边第一个比它大的，差值小于K的，和第一个比它小的，差值小于K的，
先证明连向它右边第一个比它大的，差值小于K的即可，因为设当前位置为i，右边有两个位置
也就是i在j前面，j在k前面，那么i在k前面这个条件显然没用，所以舍去，
那么全局只有2n条边，
复杂度：
Code
#include <cstdio>
#include <algorithm>
#include <queue>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
using namespace std;
const int N=500500;
int read(int &n)
{
char ch=' ';int q=0,w=1;
for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
if(ch=='-')w=-1,ch=getchar();
for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
int a[N];
int b[N*4];
int B[N*2][2],A[N],B0;
int b1[N],Ans[N];
priority_queue<int>d;
int min(int q,int w){return(q)>(w)?(w):(q);}
int max(int q,int w){return(q)<(w)?(w):(q);}
int find(int l,int r,int e,int l1,int r1)
{
if(l1<=l&&r<=r1)return b[e];
int t=(l+r)>>1;
if(r1<=t)return find(l,t,e*2,l1,r1);
else if(t<l1)return find(t+1,r,e*2+1,l1,r1);
else return max(find(l,t,e*2,l1,t),find(t+1,r,e*2+1,t+1,r1));
}
void change(int l,int r,int e,int l1,int l2)
{
if(l==r){b[e]=max(b[e],l2);return;}
int t=(l+r)>>1;
if(l1<=t)change(l,t,e*2,l1,l2);
else change(t+1,r,e*2+1,l1,l2);
b[e]=max(b[e*2],b[e*2+1]);
}
void link(int q,int w){B[++B0][0]=A[q],A[q]=B0,B[B0][1]=w,b1[w]++;}
int main()
{
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
int q,w;
read(n),read(m);
fo(i,1,n)a[read(q)]=i;
m--;
fo(i,1,n)
{
q=find(1,n,1,a[i],a[i]+m);
if(q&&q<=n)link(a[q],a[i]);
q=find(1,n,1,a[i]-m,a[i]);
if(q&&q<=n)link(a[q],a[i]);
change(1,n,1,a[i],i);
}
fo(i,1,n)if(!b1[i])d.push(-i);
ans=0;
for(;!d.empty();)
{
q=-d.top();d.pop();
efo(i,q)if(!(--b1[B[i][1]]))d.push(-B[i][1]);
Ans[q]=++ans;
}
fo(i,1,n)printf("%d\n",Ans[i]);
return 0;
}