CF1381B Unmerge

给定两个长度分别为 $n$ 和 $m$ 的数组 $a$ 和 $b$，且两者没有任何相同的元素。我们可以递归地定义一个新数组 $\mathrm{merge}(a,b)$，其长度为 $n+m$，规则如下： - 如果其中一个数组为空，则结果为另一个数组。即 $\mathrm{merge}(\emptyset,b)=b$，$\mathrm{merge}(a,\emptyset)=a$。特别地，$\mathrm{merge}(\emptyset,\emptyset)=\emptyset$。 - 如果两个数组都非空，且 $a_1 < b_1$，则 $\mathrm{merge}(a,b)=[a_1]+\mathrm{merge}([a_2,\ldots,a_n],b)$。也就是说，删除 $a$ 的第一个元素 $a_1$，合并剩余的数组，然后将 $a_1$ 加到结果的开头。 - 如果两个数组都非空，且 $a_1 > b_1$，则 $\mathrm{merge}(a,b)=[b_1]+\mathrm{merge}(a,[b_2,\ldots,b_m])$。也就是说，删除 $b$ 的第一个元素 $b_1$，合并剩余的数组，然后将 $b_1$ 加到结果的开头。 该算法有一个很好的性质：如果 $a$ 和 $b$ 都是有序的，那么 $\mathrm{merge}(a,b)$ 也是有序的。例如，它被用作归并排序的子过程。然而，在本题中，我们也考虑对无序数组应用同样的过程。例如，如果 $a=[3,1]$，$b=[2,4]$，则 $\mathrm{merge}(a,b)=[2,3,1,4]$。 一个排列是一个长度为 $n$ 的数组，包含 $1$ 到 $n$ 的 $n$ 个不同整数，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 出现了两次），$[1,3,4]$ 也不是排列（$n=3$ 但数组中有 $4$）。 现在给定一个长度为 $2n$ 的排列 $p$。请判断是否存在两个长度为 $n$ 且没有公共元素的数组 $a$ 和 $b$，使得 $p=\mathrm{merge}(a,b)$。

第一行包含一个整数 $t$（$1\le t\le 1000$），表示测试用例的数量。接下来的 $2t$ 行描述每个测试用例。 每个测试用例的第一行包含一个整数 $n$（$1\le n\le 2000$）。 每个测试用例的第二行包含 $2n$ 个整数 $p_1,\ldots,p_{2n}$（$1\le p_i\le 2n$）。保证 $p$ 是一个排列。 保证所有测试用例中 $n$ 的总和不超过 $2000$。

对于每个测试用例，如果存在长度为 $n$ 且没有公共元素的数组 $a$ 和 $b$，使得 $p=\mathrm{merge}(a,b)$，输出 "YES"；否则输出 "NO"。

在第一个测试用例中，$[2,3,1,4]=\mathrm{merge}([3,1],[2,4])$。 在第二个测试用例中，可以证明 $[3,1,2,4]$ 不是两个长度为 $2$ 的数组合并的结果。 在第三个测试用例中，$[3,2,6,1,5,7,8,4]=\mathrm{merge}([3,2,8,4],[6,1,5,7])$。 在第四个测试用例中，$[1,2,3,4,5,6]=\mathrm{merge}([1,3,6],[2,4,5])$，例如。 由 ChatGPT 4.1 翻译