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|<|T|$ 且 $(S_1,S_2,\ldots,S_{|S|})=(T_1,T_2,\ldots,T_{|S|})$。
2. 存在整数 $1\leq i\leq \min\lbrace |S|,|T| \rbrace$，使得以下两点都成立：
   • $(S_1,S_2,\ldots,S_{i-1})=(T_1,T_2,\ldots,T_{i-1})$。
   • $S_i$ 小于 $T_i$（按数值比较）。

输入以如下格式从标准输入读入：

$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 翻译