AT_arc160_a.[ARC160A] Reverse and Count

给定一个 $ (1,\ 2,\ \dots,\ N) $ 的排列 $ A = (A_1,\ A_2,\ \dots,\ A_N) $。

对于满足 $ 1 \leq L \leq R \leq N $ 的整数对 $ (L,\ R) $，定义 $ f(L,\ R) $ 为将 $ A $ 的第 $ L $ 个到第 $ R $ 个元素反转后得到的排列。

这里，“将 $ A $ 的第 $ L $ 个到第 $ R $ 个元素反转”是指将 $ A_L, A_{L+1}, \dots, A_{R-1}, A_R $ 同时替换为 $ A_R, A_{R-1}, \dots, A_{L+1}, A_L $。

满足 $ 1 \leq L \leq R \leq N $ 的 $ (L,\ R) $ 的选法共有 $ \frac{N(N+1)}{2} $ 种。

请将所有这样的 $ (L,\ R) $ 对应的排列 $ f(L,\ R) $ 全部枚举出来，并按字典序排序，输出第 $ K $ 个排列。

数列的字典序定义如下：对于数列 $ S = (S_1,S_2,\ldots,S_{|S|}) $ 和 $ T = (T_1,T_2,\ldots,T_{|T|}) $，若满足以下 1. 或 2.，则称 $ 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 $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

设按字典序排序后，第 $ K $ 个排列为 $ B = (B_1, B_2, \dots, B_N) $。

请按如下格式输出 $ B $：

$ B_1 $ $ B_2 $ $ \dots $ $ B_N $

数据范围

• $ 1 \leq N \leq 7000 $
• $ 1 \leq K \leq \frac{N(N+1)}{2} $
• $ A $ 是 $ (1,\ 2,\ \dots,\ N) $ 的一个排列

样例解释 1

将所有满足 $ 1 \leq L \leq R \leq 3 $ 的 $ (L,\ R) $ 对应的排列 $ f(L,\ R) $ 枚举如下：

• $ f(1, 1) = (1, 3, 2) $
• $ f(1, 2) = (3, 1, 2) $
• $ f(1, 3) = (2, 3, 1) $
• $ f(2, 2) = (1, 3, 2) $
• $ f(2, 3) = (1, 2, 3) $
• $ f(3, 3) = (1, 3, 2) $

将它们按字典序排序后，第 $ 5 $ 个排列是 $ f(1, 3) = (2, 3, 1) $，因此输出该排列。

样例解释 2

答案为 $ f(1, 5) $。

由 ChatGPT 4.1 翻译