P14937 「FAOI-R10」XOR Problem

• P14937
• 求出异或前缀和，题意转化为找 \(m\) 个右端点，设为 \(a_1,a_2,...,a_m\) ， \(a_0\) 为 \(0\) ，即求所有 \(a_i\oplus a_{i-1}\) 的按位与最大。
• 从高位往低位贪心，每次等于判断一个数 \(x\) 能否是所有 \(a_i\oplus a_{i-1}\) 的子集，即 \(x\) 的每一位(为 \(1\) 的)在 \(a\) 中是 \(0 1\) 交替出现的，由于 \(a_0\) 是 \(0\) ，所以是所有奇数下标的 \(a_i\&x=x\) ，偶数下标的 \(a_i\&x=0\) ，每次贪心选最前的端点，注意必须选 \(n\) ，于是做完了。