题解

思路

钱数始终是 $2^s$。固定猜测值 $a$ 后，令

$$w_i=\begin{cases}1,&x_i=a,\\-1,&x_i\ne a.\end{cases}$$

选择区间后的指数就是 $\sum_{i=l}^r w_i$，因此目标是对所有可能的 $a$ 求最大子段和。

最优区间的左右端点一定都是 $a$ 的出现位置。设 $a$ 的相邻出现位置为 $p_{j-1},p_j$，从前一个出现位置扩展到当前位置会增加一个猜中，并跨过 $p_j-p_{j-1}-1$ 个猜错位置。

做法

对每个不同的值保存其出现位置。扫描某个值的出现序列，维护以当前出现位置结尾的最佳指数 current 及其左端点：

$$current\leftarrow current-(p_j-p_{j-1}-1)+1.$$

若扩展后的值小于 $1$，就在 $p_j$ 重新开始。用所有值的最佳结果更新全局答案即可。

极小规模可以枚举 $a,l,r$；中等规模可以对每个不同的 $a$ 在原数组上跑一次 Kadane；满分算法只扫描各值的出现位置。

正确性证明

固定 $a$ 后，每次猜中使指数加一，猜错使指数减一，所以任意区间的收益指数恰为对应 $\pm1$ 序列的区间和。

若一个正收益最优区间的端点不是 $a$，删去该端点会使区间和增加，因此最优端点必为 $a$ 的出现位置。出现位置扫描中的递推准确计算“保留此前最优后缀并跨过间隔”与“在当前位置重新开始”二者的较大值，这就是 Kadane 递推在压缩序列上的形式。

算法对每个可能的 $a$ 求出其最大区间和，再在所有值之间取最大，因此输出三元组达到全局最优钱数。

复杂度分析

建立有序映射并扫描全部出现位置，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。