Standard Solution.

第一小题（$50$ 分）

第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n!)$。

第二部分（$30$ 分）

很明显，$p$ 和 $q$ 的字典序相差越大，FPT 的总时间开销越大，因此最坏情况是 $p=\{1,2,\ldots,n\}$ 和 $q=\{n,n-1,\ldots,1\}$。

此外，当 next_permutation 函数的时间开销不小于 $O(k)$ 时，序列的最后 $k$ 个数刚好是降序排列的。

在最坏情况中，每种排列（共 $n!$ 个）都会在 FPT 的过程中出现一次，序列的最后 $k$ 个数以任意大小关系出现的频率都相等，因此它们刚好降序排列的频率是 $\dfrac{1}{k!}$。此时总的时间复杂度是：

$$n! \times \sum _{i=1} ^n \large{(}\normalsize(\dfrac{1}{i!}-\dfrac{1}{(i+1)!}) \times O(i)\large{)} $$

将括号展开（最后一项小于 $1$，本来就不存在，因此舍去）：

$$n! \times \sum _{i=1} ^n \large{(}\normalsize\dfrac{1}{i!} \times O(1)\large{)} $$

这是一个经典的求和问题，它的答案总是小于：

$$n! \times O(e)$$

因为 $e=2.71828\ldots$ 是常数，所以总的时间复杂度是 $O(n!)$。

第三部分（$10$ 分）

以下是一组可能的数据：

• $p=\{1,2,\ldots,n\}$。
• $q=\{n,n-1,\ldots,1\}$。

第二小题（$50$ 分）

第一部分（$10$ 分）

此时 FPT 的最坏时间复杂度是 $O(n^2)$。

第二部分（$30$ 分）

让我们再来看看 $p=\{1,2,\ldots,n\}$ 和 $q=\{n,n-1,\ldots,1\}$ 的情况。此时 FPT 的时间复杂度是 $O(n^2)$：

可以发现，每调用一次 next_permutation 函数，整个排列的逆序对个数最多增加 $1$。

由于 $p$ 的逆序对个数是 $0$，$q$ 的逆序对个数是 $0+1+\ldots+(n-1)=\dfrac{n(n-1)}{2}$，故此时此时 FPT 的时间复杂度是 $O(n^2)$，而冒泡排序（每次只选择包含 $2$ 个数字的区间调用 next_permutation 函数）可以实现这一时间复杂度。

实际上，只要 $p=\{1,2,\ldots,n\}$，冒泡排序就可以在 $O(t)$ 的时间复杂度内完成变换，其中 $t$ 是 $q$ 中逆序对的个数。

接下来，让我们对任意的 $p$ 和 $q$ 设计一个策略，使得 FPT 的时间复杂度是 $O(n^2)$。

首先，忽略 $p$ 和 $q$ 的最长公共前缀，因为它们不需要变换。

忽略它们的最长公共前缀后，设排列中剩下 $m$ 个数，则用冒泡排序给后 $m-1$ 个数排降序。

接下来，设 $p$ 中的第一个数字为 $x$，$q$ 中的第一个数字为 $y$，分两种情况讨论：

• 如果 $y=x+1$，我们对整个排列 $p$ 调用一次 next_permutation 函数，使得数字 $y$ 变成排列 $p$ 中的第一个数字（其他数字升序排列），然后用冒泡排序对后 $m-1$ 个数进行变换。
• 否则，只要我们先对 $p$ 中以数字 $y-1$ 为右端点的前缀 $r$ 调用一次 next_permutation 函数，使得数字 $y-1$ 变成排列 $p$ 中的第一个数字（其他数字升序排列），再用冒泡排序对后 $m-1$ 个数排降序，就可以按第一种情况处理了。

整个过程一共进行了 $3$ 次冒泡排序，因此总的时间复杂度是 $O(n^2)$。

第三部分（$10$ 分）

以下是一组可能的数据：

• $p=\{1,2,\ldots,n\}$。
• $q=\{n,n-1,\ldots,1\}$。