这是一道 CF 2040C - Ordered Permutations 的构造题。
下面给出详细题解。

---

题目大意

定义长度为 $n$ 的排列 $p$ 的分数：

[ S(p) = \sum_{l=1}^{n} \sum_{r=l}^{n} \min(p_l, p_{l+1}, \dots, p_r) ]

在 $S(p)$ 最大的所有排列中，按字典序从小到大排列，输出第 $k$ 个排列。

---

关键结论（分析部分）

1. 最大 $S(p)$ 的排列结构

可以证明，$S(p)$ 取最大值的排列是 单峰排列（先递增后递减），并且最大值 $n$ 在中间。
更精确地说：

• 将数字 $1, 2, \dots, n$ 依次放入排列中。
• 每个新数字 $i$ 必须放在当前已放数字区间的 最左空位 或 最右空位。
• 这样形成的排列，其形状是：先递增到 $n$，再递减（或者说“山脉形”）。

原因：
当放入 $i$ 时，它成为所有包含它的区间的最小值，贡献 $(n-i+1)$ 次最小值，这种放法最大化总 $S(p)$。

---

2. 排列数量

由于每个数字 $i$（除了 $n$）都有两种选择（放最左或最右），所以 $\text{总数} = 2^{n-1}$。

例如 $n=3$，$2^{2}=4$ 个最大排列：
$[1,2,3]$, $[1,3,2]$, $[2,3,1]$, $[3,2,1]$
（验证示例中 $[2,1,3]$ 和 $[3,1,2]$ 未出现，因为它们的 $S(p)$ 更小）

---

3. 字典序与二进制编码

从左到右处理数字 $1, 2, \dots, n-1$：

• 放左边 $\to$ 对应二进制位 $0$（加入左序列）
• 放右边 $\to$ 对应二进制位 $1$（加入右序列）

数字 $n$ 最后放在中间。
这样，从 $0$ 到 $2^{n-1}-1$ 的二进制数唯一对应一个最大排列，且按二进制顺序就是字典序顺序（需要验证，结论成立）。

因此：

• 第 $k$ 个（从 $1$ 开始计数）对应的二进制是 $k-1$（$n-1$ 位）。

---

算法步骤（对应标程）

1. 读入 $n, k$。
2. 如果 $n \le 60$ 且 $2^{n-1} < k$，输出 $-1$（情况不足）。
3. 令 $k = k-1$（转为 $0$-based 索引）。
4. 将 $k$ 转换成二进制，不足 $n-1$ 位前面补 $0$。
5. 从左到右扫描二进制位（实际代码是从高位到低位）：
   • 若某位 $=0$：当前数字放入左序列 a
   • 若某位 $=1$：当前数字放入右序列 b
6. 输出：左序列 a → 数字 $n$ → 右序列 b（逆序输出，以保证构造正确）。

---

示例验证

示例 1：$n=3, k=2$

$n-1=2$ 位，$k-1=1$，二进制 01（高位到低位）。

处理 $i=1$：

• 左对 (i=1, ) 位 0 → 左 [1]
• 右对 (i=2, ) 位 1 → 右 [2]

输出：左 [1]，然后 3，然后右逆序 [2] → 1 3 2 ✅

---

示例 2：$n=3, k=3$

$k-1=2$，二进制 10。

$i=1$，位 1 → 右 [1]
$i=2$，位 0 → 左 [2]

输出：左 [2] → 3 → 右逆序 [1] → 2 3 1 ✅

---

示例 3：$n=4, k=11$

$n-1=3$，$2^{3}=8 < 11$ → 输出 -1 ✅

---

复杂度

• 每个测试 $O(n)$ 时间
• 总 $n$ 和 $\le 2\cdot 10^5$，可以通过
• 注意 $2^{n-1}$ 可能溢出，这里只处理 $n \le 60$ 时比较

---

代码复现（加注释）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        long long k;   // k up to 1e12
        cin >> n >> k;
        
        // 总排列数 = 2^(n-1)
        if (n <= 60 && (1ll << (n - 1)) < k) {
            cout << -1 << endl;
            continue;
        }
        
        k--;  // 0-based index
        
        // 得到二进制表示（低位在 vector 前面）
        vector<int> d;
        while (k) {
            d.push_back(k % 2);
            k /= 2;
        }
        // 补足 n-1 位
        while (d.size() < n - 1) d.push_back(0);
        
        // 现在 d[0] 是最高位？实际是低位在左，我们要从高位(大索引)处理
        // 标程从 i = n-2 往下走，正是从高位向低位
        vector<int> a, b;
        for (int i = n - 2, j = 1; i >= 0; i--, j++) {
            if (d[i] == 0) a.push_back(j);
            else b.push_back(j);
        }
        
        reverse(b.begin(), b.end());
        for (int x : a) cout << x << ' ';
        cout << n << ' ';
        for (int x : b) cout << x << ' ';
        cout << endl;
    }
    return 0;
}

---

总结思想

• 最大 $S(p)$ 的排列是 单峰形（先升后降）。
• 构造时数字 $1$ 到 $n-1$ 依次选左或右，$n$ 在中间。
• 字典序对应二进制编码 $k-1$。
• 解为：左段（升序） + $n$ + 右段（降序）。