#P13148. [ARC114F] Permutation Division

    ID: 12332 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400贪心二分数据结构排序构造前缀和后缀数组

[ARC114F] Permutation Division

题目描述

给定一个 1,2,⋯ ,N1, 2, \cdots, N 的排列 PP。

你可以将 PP 恰好分割成 KK 个非空的连续子序列,方式任意。

maroon 君会将你分割出的连续子序列重新排列并连接起来,得到一个新的排列 QQ。maroon 君会选择使 QQ 字典序最大的排列方式。

你希望 QQ 的字典序尽可能小。请输出你在最优分割下得到的 QQ。

输入格式

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

NN KK P1P_1 P2P_2 ⋯\cdots PNP_N

输出格式

请输出你最优分割下得到的 QQ。

输入输出样例 #1

输入 #1

3 2
1 2 3

输出 #1

2 3 1

输入输出样例 #2

输入 #2

4 3
4 3 1 2

输出 #2

4 3 1 2

输入输出样例 #3

输入 #3

20 7
10 5 8 2 1 9 12 20 15 3 7 6 19 4 11 17 13 14 16 18

输出 #3

10 5 8 2 7 6 19 4 11 17 13 14 16 18 3 1 9 12 20 15

说明/提示

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤N1 \leq K \leq N
  • 1≤Pi≤N1 \leq P_i \leq N
  • Pi≠Pj (i≠j)P_i \neq P_j\ (i \neq j)
  • 输入均为整数

样例解释 1

对于 PP 的分割方式,可以是 (1,2),(3)(1, 2), (3) 或 (1),(2,3)(1), (2, 3)。
前者情况下,maroon 君会将 (3),(1,2)(3), (1, 2) 重新排列,得到 Q=(3,1,2)Q = (3, 1, 2)。
后者情况下,maroon 君会将 (2,3),(1)(2, 3), (1) 重新排列,得到 Q=(2,3,1)Q = (2, 3, 1)。
因此,你应该选择后者的分割方式。