题解

思路

从左到右处理数组。处理完位置 $i$ 后，把 $i$ 所在的颜色称为“当前颜色”，另一种颜色称为“另一颜色”。红、蓝本身完全对称，因此不必记录具体颜色，只需记录另一颜色最后一个数的值 $x$。

设状态值 $f_x$ 表示处理完当前位置、另一颜色最后一个数为 $x$ 时的最大得分。用 $x=0$ 表示另一颜色尚未出现；由于所有 $A_i$ 都是正数，这个哨兵不会与合法值混淆。

转移

设上一个数为 $p$，当前读到 $y$。

如果继续使用当前颜色，所有状态都保留 $x$；仅当 $p=y$ 时统一增加 $y$。

如果切换颜色，切换前另一颜色的最后一个值若等于 $y$，当前数贡献 $y$，否则贡献 $0$。切换后，新的“另一颜色”最后一个值变为 $p$。因此切换所得的最好值为

它只会更新下标 $p$ 对应的状态。

做法

每一步只需要四种操作：全体状态加同一个数、查询全局最大值、查询一个值、对一个值取最大。令实际状态为 $f_x=g_x+tag$，其中 $tag$ 保存全局增量，再单独维护所有 $g_x$ 的最大值即可在常数时间完成一次转移。

值域不超过 $10^6$，可用数组和时间戳记录被访问过的 $g_x$，避免每组数据清空整个值域。初始时只有 $g_0=0$，最终答案是全局最大的 $g_x+tag$。

正确性证明

对处理位置数作归纳。初始只处理 $A_1$ 时，两种颜色等价，另一颜色为空，状态 $f_0=0$ 完整描述所有方案。

假设处理完 $i-1$ 后，每个 $f_x$ 都等于其定义下所有染色方案的最优得分。位置 $i$ 只有两种选择：保持与 $i-1$ 相同的颜色，或切换到另一颜色。保持颜色时，另一颜色末值不变，贡献恰由 $A_{i-1}=A_i$ 决定；切换颜色时，原另一颜色末值决定贡献，且切换后的另一颜色末值恰为 $A_{i-1}$。转移分别枚举并取这两类方案的最大值，没有遗漏，也不会加入不合法方案。因此归纳成立，最终全局最大状态就是所有染色方案的最大得分。

复杂度

每个位置只进行常数次操作。单组数据时间复杂度为 $O(n)$，额外空间复杂度为 $O(V)$，其中 $V=10^6$。