CF2158B Split

给定一个包含 $2n$ 个整数的序列 $a$。定义 $f(b)$ 表示序列 $b$ 中出现次数为奇数的不同元素个数。你需要将所给数组划分为两个互不相交的子序列 $p$ 和 $q$，每个子序列的大小均为 $n$，使得 $f(p) + f(q)$ 的值最大。请输出最大值。 一个序列 $a$ 是序列 $b$ 的子序列，如果 $a$ 可以通过从 $b$ 中删除若干（可能为零或全部）位置的元素得到。

每个测试点包含多组测试数据。第一行包含测试数据组数 $t$（$1 \le t \le 10^4$）。 接下来每组测试数据包含两行： 第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。 第二行包含 $2n$ 个整数 $a_1,a_2,\ldots,a_{2n}$（$1 \le a_i \le 2n$），即序列 $a$ 的元素。 保证所有测试点中 $n$ 的总和不超过 $2 \cdot 10^5$。

每组测试数据输出一行。 每行输出一个整数，表示能取得的 $f(p) + f(q)$ 的最大值。

对于第一个测试用例： - 可以将数组划分为 $p = [1, 3]$ 和 $q = [2, 4]$。 - 这样 $f(p) = 2$，$f(q) = 2$，因为每个都有两个出现次数为奇数的不同元素。 对于第二个测试用例： - 可以将数组划分为 $p = [5, 5, 5]$ 和 $q = [5, 5, 5]$。 - 这样 $f(p) = 1$，$f(q) = 1$。 对于第五个测试用例： - 可以将数组划分为 $p = [1, 2, 3, 4, 5, 6]$ 和 $q = [4, 1, 4, 1, 5, 4]$。 - 这样 $f(p) = 6$，$f(q) = 2$。 由 ChatGPT 5 翻译