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