问题 D: [CSP-S 2024] 擂台游戏

给定一个长度为 $n$ 的正整数数组 $A$，其中所有数从左至右排成一排。

你需要将 $A$ 中的每个数染成红色或蓝色之一，然后按如下方式计算最终得分：

设 $C$ 为长度为 $n$ 的整数数组，对于 $A$ 中的每个数 $A_i$（$1\le i\le n$）：

• 如果 $A_i$ 左侧没有与其同色的数，则令 $C_i=0$。
• 否则，记其左侧与其最靠近的同色数为 $A_j$，若 $A_i=A_j$，则令 $C_i=A_i$，否则令 $C_i=0$。

你的最终得分为 $C$ 中所有整数的和，即 $\sum _{i=1}^n{C}_i$。你需要最大化最终得分，请求出最终得分的最大值。

【样例 1 解释】

共有 $T=4$ 组数据，这里只解释第一组。$5$ 名选手的真实能力值为 $[1,0,0,2,1]$。$5$ 组询问分别是对长度为 $5,4,1,2,3$ 的前缀进行的。

1. 对于长度为 $1$ 的前缀，由于只有 $1$ 号一个人，因此答案为 $1$。
2. 对于长度为 $2$ 的前缀，由于 $2$ 个人已经是 $2$ 的幂次，因此不需要进行扩充。根据抽签 $d_{1,1}=1$ 可知 $2$ 号为擂主，由于 $a_2<1$，因此 $1$ 号获胜，答案为 $1$。
3. 对于长度为 $3$ 的前缀，首先 $1$ 号、$2$ 号比赛是 $1$ 号获胜（因为 $d_{1,1}=1$，故 $2$ 号为擂主，$a_2<1$），然后虽然 $4$ 号能力值还不知道，但 $3$ 号、$4$ 号比赛一定是 $4$ 号获胜（因为 $d_{1,2}=0$，故 $3$ 号为擂主，$a_3<1$），而决赛 $1$ 号、$4$ 号谁获胜都有可能（因为 $d_{2,1}=1$，故 $4$ 号为擂主，如果 $a_4<2$ 则 $1$ 号获胜，$a_4\ge 2$ 则 $4$ 号获胜）。综上所述，答案为 $1+4=5$。
4. 对于长度为 $4$ 的前缀，我们根据上一条的分析得知，由于 $a_4\ge 2$ ，所以决赛获胜的是 $4$ 号。
5. 对于长度为 $5$ 的前缀，可以证明，可能获胜的选手包括 $4$ 号、$7$ 号、$8$ 号，答案为 $19$。

因此，该组测试数据的答案为 $(1\times 19)\oplus (2\times 4)\oplus (3\times 1)\oplus (4\times 1)\oplus (5\times 5)=5$。

【数据范围】

对于所有测试数据，保证：$2\le n,m\le 10^5$，$0\le a_i,X_j<2^{31}$，$1\le c_i\le n$，$1\le T\le 256$。

特殊性质 A：保证询问的 $c_i$ 均为 $2$ 的幂次。

特殊性质 B：保证所有的 $d_{R,G}=0$。

本题有多组测试数据。

输入的第一行包含一个正整数 $T$，表示数据组数。

接下来包含 $T$ 组数据，每组数据的格式如下：

第一行包含一个正整数 $n$，表示数组长度。

第二行包含 $n$ 个正整数 $A_1,A_2,\dots ,A_n$，表示数组 $A$ 中的元素。

3
3
1 2 1
4
1 2 3 4
8
3 5 2 5 1 2 1 4

1
0
8