[AGC001F] Wide Swap

题意翻译

给出一个元素集合为$\{1,2,\dots,N\}$ $(1\leq N\leq 500,000)$的排列$P$,当有$i,j$ $(1\leq i<j\leq N)$满足$j-i\geq K$ $(1\leq K\leq N-1)$且$|P_{i}-P_{j}|==1$时,可以交换$P_{i}$和$P_{j}$ 求:可能排列中字典序最小的排列 输入格式: $N$ $K$ $P_{1}$ $P_{2}$ $\dots$ $P_{N}$

题目描述

[problemUrl]: https://agc001.contest.atcoder.jp/tasks/agc001_f 長さ $ N $ の、 $ 1\ ~\ N $ をちょうど $ 1 $ つずつ含む数列 $ P_1\ ...\ P_N $ が与えられます。 あなたはこの数列に対し、以下のような操作を何度でも行えます。 - 整数 $ i,j\ (1\ ≦\ i\ <\ j\ ≦\ N) $ を選ぶ。 - $ P_i $ と $ P_j $ の値を入れ替える。 - ただしこのとき、 $ j\ -\ i\ ≧\ K $ かつ $ |P_i\ -\ P_j|\ =\ 1 $ を満たしていなければならない。 このような操作によって作ることのできる数列のうち、辞書順最小のものを求めてください。

输入输出格式

输入格式


The input is given from Standard Input in the following format: ``` $ N $ $ K $ $ P_1 $ $ P_2 $ $ ... $ $ P_N $ ```

输出格式


Print the lexicographically smallest permutation that can be obtained.

输入输出样例

输入样例 #1

4 2
4 2 3 1

输出样例 #1

2
1
4
3

输入样例 #2

5 1
5 4 3 2 1

输出样例 #2

1
2
3
4
5

输入样例 #3

8 3
4 5 7 8 3 1 2 6

输出样例 #3

1
2
6
7
5
3
4
8

输入样例 #4

4 2
4 2 3 1

输出样例 #4

2
1
4
3

输入样例 #5

5 1
5 4 3 2 1

输出样例 #5

1
2
3
4
5

输入样例 #6

8 3
4 5 7 8 3 1 2 6

输出样例 #6

1
2
6
7
5
3
4
8

说明

### 制約 - $ 2≦N≦500,000 $ - $ 1≦K≦N-1 $ - $ P $ は $ 1,\ 2,\ ...,\ N $ の順列である。 ### Problem Statement You are given a permutation $ P_1\ ...\ P_N $ of the set { $ 1 $ , $ 2 $ , ..., $ N $ }. You can apply the following operation to this permutation, any number of times (possibly zero): - Choose two indices $ i,j\ (1\ ≦\ i\ <\ j\ ≦\ N) $ , such that $ j\ -\ i\ ≧\ K $ and $ |P_i\ -\ P_j|\ =\ 1 $ . Then, swap the values of $ P_i $ and $ P_j $ . Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one. ### Constraints - $ 2≦N≦500,000 $ - $ 1≦K≦N-1 $ - $ P $ is a permutation of the set { $ 1 $ , $ 2 $ , ..., $ N $ }. ### Sample Explanation 1 以下のような手順で操作を行えば良いです。 - $ 4\ 2\ 3\ 1 $ - $ 4\ 1\ 3\ 2 $ - $ 3\ 1\ 4\ 2 $ - $ 2\ 1\ 4\ 3 $ ### Sample Explanation 4 One possible way to obtain the lexicographically smallest permutation is shown below: - $ 4\ 2\ 3\ 1 $ - $ 4\ 1\ 3\ 2 $ - $ 3\ 1\ 4\ 2 $ - $ 2\ 1\ 4\ 3 $