P16595 [GKS 2016 #E] Sorting Array

我们正在设计一种有点另类的排序算法，用于对包含 $1$ 到 $N$ 所有整数的数组 $A$ 进行排序。$A$ 中的整数最初可以是任意顺序。除了输入顺序外，该算法还依赖于两个整数 $P$（$P$ 不超过 $3$）和 $K$。算法的执行过程如下： 1. 将 $A$ 划分为 $K$ 个互不相交的非空子数组 $A_1, A_2, \dots, A_K$，使得按顺序 $A_1 A_2 \dots A_K$ 拼接起来恰好得到 $A$。 2. 分别对每个子数组进行排序。 3. 选择至多 $P$ 个子数组，并任意多次交换这些子数组中的任意两个。 例如，考虑 $A = [1 \ 5 \ 4 \ 3 \ 2]$ 且 $P = 2$。一种可能的划分为 $K = 4$ 个互不相交的子数组： ``` A1 = [1] A2 = [5] A3 = [4] A4 = [3 2] 排序后： A1 = [1] A2 = [5] A3 = [4] A4 = [2 3] 交换 A4 与 A2 后： A1 = [1] A2 = [2 3] A3 = [4] A4 = [5] ``` 我们希望通过以下方式证明该算法适用于分布式环境：对于给定的输入和 $P$ 值，找出最大的分区数 $K$，使得通过合理选择分区和交换，可以将原始顺序排序。你能帮助我们计算出这个 $K$ 吗？

输入的第一行给出测试用例的数量 $T$。 接下来有 $T$ 个测试用例。每个测试用例由两行组成。第一行包含两个整数 $N$ 和 $P$，含义如上所述。 测试用例的第二行包含 $N$ 个整数 $X_1, X_2, \dots, X_N$，表示数组 $A$。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是参数 $K$ 的最大可能值。

样例 #1： 与题目描述中的例子相同。 样例 #2： $[4 \ 5] \ [1 \ 2 \ 3]$ 交换两个块：$[1 \ 2 \ 3] \ [4 \ 5]$ 样例 #3： $[6] \ [3 \ 5 \ 2 \ 4] \ [1]$ 对 $[3 \ 5 \ 2 \ 4]$ 排序，然后交换 $[6]$ 与 $[1]$，得到：$[1] \ [2 \ 3 \ 4 \ 5] \ [6]$ 样例 #4： $[4 \ 5] \ [1] \ [2 \ 3]$ 交换 $[4 \ 5]$ 与 $[1]$，然后交换 $[2 \ 3]$ 与 $[4 \ 5]$：$[1] \ [2 \ 3] \ [4 \ 5]$ 样例 #5： $[1] \ [2] \ [6] \ [4] \ [5] \ [3]$ 交换 $[6]$ 与 $[3]$：$[1] \ [2] \ [3] \ [4] \ [5] \ [6]$ **注意**：前 $3$ 个样例不会出现在大数据集中，后 $2$ 个样例不会出现在小数据集中。 ### 限制条件 $1 \le T \le 100$。 $1 \le N \le 5000$。 对所有 $i$，$1 \le X_i \le N$。 对所有 $i \ne j$，$X_i \ne X_j$。 **小数据集（测试集 1 – 可见）** $P = 2$。 **大数据集（测试集 2 – 隐藏）** $P = 3$。 翻译由 DeepSeek V4 Pro 完成