D.Birthday Gift

Problem 1946D - Birthday Gift

分析

对于区间位运算，比较自然的做法是按位拆分，并从高位到低位分析 $x$ 的每一位。

1. 如果第 $i$ 位为 $0$，并且数组中这一位为 $1$ 的元素个数为奇数，那么无论如何分段，都会有一段的异或结果在这一位为 $1$，从而导致整体大于 $x$。

2. 如果第 $i$ 位为 $0$，并且这一位为 $1$ 的元素个数为偶数，则需要尽量就近两两合并，保证这一位异或为 $0$，同时让分组数量尽可能多。

3. 如果第 $i$ 位为 $1$，并且这一位为 $1$ 的元素个数为奇数，则当前位不需要强制处理，可以继续向低位传递。

4. 如果第 $i$ 位为 $1$，并且这一位为 $1$ 的元素个数为偶数，则两两合并可以保证这一位异或为 $0$，并得到一个候选答案；但不合并也可能在低位获得更多分组，所以也要把“不处理”的情况继续向后传递。

由于第 4 种情况里会保留与 $x$ 当前前缀相等的状态，可以考虑对 $x$ 加一后再处理，这样在传递到低位时能统一处理边界。