AT_arc165_b [ARC165B] Sliding Window Sort 2

给定一个由 $1$ 到 $N$ 的整数构成的排列 $P=(P_1,P_2,\dots,P_N)$ 和一个整数 $K$。 对于排列 $P$，我们定义如下操作： - 选择一个满足 $1\leq i\leq N-K+1$ 的整数 $i$，将 $P_i,P_{i+1},\dots,P_{i+K-1}$ 按升序排列。也就是说，设 $P_i,P_{i+1},\dots,P_{i+K-1}$ 升序排列后为 $(x_1,x_2,\dots,x_K)$，则对于每个 $1\leq j\leq K$，用 $x_j$ 替换 $P_{i+j-1}$。 请你求出对 $P$ 恰好进行一次上述操作后，能够得到的排列中字典序最大的一个，并用空格分隔输出。 数列的字典序定义如下：设数列 $S=(S_1,S_2,\ldots,S_{|S|})$，$T=(T_1,T_2,\ldots,T_{|T|})$，则 $S$ 的字典序小于 $T$，当且仅当满足以下两条之一。这里 $|S|,|T|$ 分别表示 $S,T$ 的长度。 1. $|S|

输入以如下格式从标准输入读入： > $N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$

请输出对 $P$ 恰好进行一次操作后能得到的字典序最大的排列，数之间用空格分隔。

### 限制 - $1\leq K\leq N\leq 2\times 10^5$ - $1\leq P_i\leq N$ - $(P_1,P_2,\dots,P_N)$ 是 $1$ 到 $N$ 的一个排列 - 输入的所有值均为整数 ### 样例解释 1 当 $i=1$ 时，操作的区间为 $(P_1,P_2,P_3)=(2,1,4)$，升序排列后为 $(1,2,4)$，所以 $P_1,P_2,P_3$ 分别变为 $1,2,4$，此时 $P=(1,2,4,3)$。 当 $i=2$ 时，操作的区间为 $(P_2,P_3,P_4)=(1,4,3)$，升序排列后为 $(1,3,4)$，此时 $P=(2,1,3,4)$。 这两种结果中，字典序较大的是 $(2,1,3,4)$，因此答案为 $(2,1,3,4)$。 由 ChatGPT 4.1 翻译