CF1870E Another MEX Problem

给定一个长度为 $n$ 的整数数组 $a$。你可以选择若干组不重叠的子数组（注意，某些元素可以不被包含在任何子数组中，这是允许的）。对于每个被选中的子数组，计算其 MEX（最小未出现的非负整数），然后将所有得到的 MEX 值进行按位异或（XOR）运算。你能获得的最大异或值是多少？ MEX（minimum excluded）指的是一个数组中未出现的最小非负整数。例如： - $[2,2,1]$ 的 MEX 是 $0$，因为 $0$ 没有出现在数组中。 - $[3,1,0,1]$ 的 MEX 是 $2$，因为 $0$ 和 $1$ 出现在数组中，但 $2$ 没有。 - $[0,3,1,2]$ 的 MEX 是 $4$，因为 $0$、$1$、$2$ 和 $3$ 都出现了，但 $4$ 没有。

第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i \leq n$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $5000$。

对于每个测试用例，输出一个整数，表示所能获得的最大 MEX 值异或和。

在第一个测试用例中，如果我们取整个数组，最大异或值为 $2$，因为 $\operatorname{MEX}([1, 0]) = 2$。 在第二个测试用例中，如果我们将数组分成 $[1, 2, 0]$ 和 $[7, 1, 2, 0, 2, 4, 3]$ 两段，最大异或值为 $6$： - $\operatorname{MEX}([1, 2, 0]) = 3$， - $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$， 因此异或值为 $5 \oplus 3 = 6$。 在第三个测试用例中，如果我们将数组分成 $[1, 0]$ 和 $[7, 1, 2, 0, 2, 4, 3]$ 两段，最大异或值为 $7$： - $\operatorname{MEX}([1, 0]) = 2$， - $\operatorname{MEX}([7, 1, 2, 0, 2, 4, 3]) = 5$， 因此异或值为 $5 \oplus 2 = 7$。 由 ChatGPT 4.1 翻译