CF2040C.Ordered Permutations

给定一个长度为 $n$ 的整数排列 $p_1, p_2, \ldots, p_n$，其中包含从 $1$ 到 $n$ 的所有整数。我们定义一个如下的和式：

$$S(p) = \sum_{1 \le l \le r \le n} \min(p_l, p_{l+1}, \ldots, p_r)$$

我们希望找出所有能使 $S(p)$ 最大的排列，并从中按字典序选择第 $k$ 个。如果这样的排列数量少于 $k$，则输出 -1。

解释说明：

• 长度为 $n$ 的排列是一个由 $n$ 个不同的整数组成的序列，这些整数来源于 $1$ 到 $n$ 的一组数字。例如，$[2, 3, 1, 5, 4]$ 是一个符合要求的排列，而 $[1, 2, 2]$ 因为有重复数字 $2$ 而不符合，$[1, 3, 4]$ 也不符合要求，因为它包含了不在 $1$ 到 $n$ 范围内的数 $4$（$n = 3$）。
• 示例计算：
  • 对于排列 $[1, 2, 3]$，$S(p)$ 计算为 $\min(1) + \min(1, 2) + \min(1, 2, 3) + \min(2) + \min(2, 3) + \min(3) = 1 + 1 + 1 + 2 + 2 + 3 = 10$。
  • 对于排列 $[2, 4, 1, 3]$，$S(p)$ 计算为 $\min(2) + \min(2, 4) + \min(2, 4, 1) + \min(2, 4, 1, 3) + \min(4) + \min(4, 1) + \min(4, 1, 3) + \min(1) + \min(1, 3) + \min(3) = 2 + 2 + 1 + 1 + 4 + 1 + 1 + 1 + 1 + 3 = 17$。
• 字典序小于：数组 $a$ 比数组 $b$ 在字典序上小的条件是：
  1. $a$ 是 $b$ 的一个前缀，且 $a \ne b$；
  2. 或者在第一个不同的位置上，$a$ 的元素小于 $b$ 的对应元素。

第一行输入一个整数 $t$，表示测试用例的数量 ($1 \le t \le 10^4$)。之后的每一个测试用例由一行组成，包含两个整数 $n$ 和 $k$，分别表示排列的长度和需要找出的第 $k$ 个排列的索引 ($1 \le n \le 2 \cdot 10^5$; $1 \le k \le 10^{12}$)。

保证所有测试用例中的 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每一个测试用例：

• 如果符合条件的排列少于 $k$ 个，则输出 -1。
• 否则，输出第 $k$ 个符合条件的排列。

以下是所有长度为 3 的排列及其对应的 $S(p)$ 值（按字典序排序）：

排列	$S(p)$ 的值
$[1, 2, 3]$	$10$
$[1, 3, 2]$	$10$
$[2, 1, 3]$	$9$
$[2, 3, 1]$	$10$
$[3, 1, 2]$	$9$
$[3, 2, 1]$	$10$

在第一个测试用例中，需输出长度为 3 的第 2 个符合条件的排列，看表格可以知道是 $[1, 3, 2]$。

在第二个测试用例中，需输出长度为 3 的第 3 个符合条件的排列，对应的是 $[2, 3, 1]$。

本翻译由 AI 自动生成