分数: 600 点
问题陈述
给你一个排列 P=(P_1,P_2,\dots,P_N) 的整数来自 1 to N 和一个整数 K.
考虑以下排列运算 P.
- 选择一个整数 i 这样 1 \leq i \leq N-K+1,并排序 P_i,P_{i+1},\dots,P_{i+K-1} 按升序排列。也就是说,让 (x_1,x_2,\dots,x_K) 是排列的结果 P_i,P_{i+1},\dots,P_{i+K-1} 按从小到大的顺序,并替换 P_{i+j-1} 与 x_j 对于每个 1 \leq j \leq K.
找到通过执行上述操作可以获得的按字典顺序排列的最大排列 P 恰好一次。
序列的字典顺序是什么?
一个序列 S = (S_1,S_2,\ldots,S_{|S|}) is 按字典顺序较小 比 T = (T_1,T_2,\ldots,T_{|T|}) 当下面的 1. 或 2. 成立时。 在这里, |S| 和 |T| 表示的长度 S 和 T。
- |S| \lt |T| 和 (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- 有一个整数 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 (作为数字)。
约束
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq P_i \leq N
- (P_1,P_2,\dots,P_N) 是以下整数的排列 1 to N.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K P_1 P_2 \dots P_N
输出
打印通过执行上述操作可以获得的按字典顺序排列的最大排列 P 恰好一次,中间有空格。
示例输入 1
4 3 2 1 4 3
示例输出 1
2 1 3 4
如果您执行操作 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,1,3,4).
按字典顺序,它们之间较大的是 (2,1,3,4),所以答案是 (2,1,3,4).
示例输入 2
5 1 3 1 4 2 5
示例输出 2
3 1 4 2 5
示例输入 3
20 7 9 4 3 1 11 12 13 15 17 7 2 5 6 20 19 18 8 16 14 10
示例输出 3
9 4 3 1 11 12 13 15 17 7 2 5 6 8 18 19 20 16 14 10