解题思路

问题要求构造一个由 $1$ 到 $n$ 的排列，使得序列中恰好有 $m$ 个「下沉」（即相邻位置满足左边元素大于右边元素的数对数量），且 $0 \le m < n$。

我们可以利用「反转前缀」的方法来简洁地构造出满足条件的序列：

1. 当 $m = 0$ 时，只需要构造一个完全升序的排列：$1, 2, \dots, n$，此时没有任何下沉。
2. 当 $m \ge 1$ 时，考虑反转前 $m+1$ 个数字组成的连续升序段 $[1, 2, \dots, m+1]$，将其变为 $[m+1, m, \dots, 1]$。在这个长度为 $m+1$ 的前缀内部，相邻元素依次是 $(m+1, m), (m, m-1), \dots, (2, 1)$，正好产生 $m$ 个下沉。
3. 前缀之后的部分保持原始顺序：$m+2, m+3, \dots, n$，这些元素与前面部分连接时，由于前缀最后一个元素是 $1$，而后面的第一个元素是 $m+2$（一定大于 $1$），因此不会新增下沉；后段内部也是升序，同样没有下沉。