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

输入

3 5
1 3 2

输出

2 3 1

样例 2

输入

5 15
1 2 3 4 5

输出

5 4 3 2 1

样例 3

输入

10 37
9 2 1 3 8 7 10 4 5 6

输出

9 2 1 6 5 4 10 7 8 3

说明/提示

数据范围

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