题目描述

对于一个长度为 $n$ 的序列 $s$,定义函数

$$f(s)=\max \lbrace (s_1 \ xor \ s_2 \ xor \ \cdots \ xor \ s_i)+(s_{i+1} \ xor \ s_{i+2} \ xor \ \cdots \ xor \ s_{n})|i \in [0, n]\rbrace$$

给定序列 $a$,求 $a$ 每个前缀的 $f$ 值。

思路

令 $s$ 为 $a$ 的前缀 $xor$,我们发现,对于 $a$ 的前缀 $i$ 项,我们要求使得 $s_j+s_j \ xor \ s_i$ 最大的 $j$。

显然,$s_i$ 为 1 的二进制位不影响答案,我们只需要考虑当 $s_i$ 的某一位为 0 时,能否贪心地找到一个 $j$ 使得这一位对答案产生贡献。

我们从高位开始,在 $s_i$ 上选取一些为 0 的位置,添加一个位置的时候判断这些位置都为 1 的 $s_j$ 是否存在。

于是维护一个 $f_i$,表示包含集合 $i$ 的 $j$ 的最小值,每次判断 $f$ 的值是否小于等于 $i$ 即可。

代码