前置知识
位运算，前缀异或和。
位运算
要解决这道题，我们只用了解一种：按位异或运算。
什么是按位异或呢？
异或：只有两个值不同时才为 1，其余状态为0。
要求按位异或时可以使用转二进制+竖式的方法.
例：求7和11的按位异或。
第一步：转二进制
7_{10}=111_2
11_{10}=1011_2
第二步：竖式计算
1011
0111
----
1100
第三步：转十进制
1100_2=12_{10}
所以7按位异或11为12。
异或有三大运算律，分别是：
- 交换律： a⊕b=b⊕a 。
- 结合律： (a⊕b)⊕c=a⊕(b⊕c) 。
- 自反律： a⊕b⊕a=b
异或在C++中为^。
前缀异或和
假设我们的数组为 a_1 到 a_n 。
现在我们新建一个数组 s 。
定义 s_i 为 a_1 \oplus a_2\,\oplus\,...\oplus\,a_i 。
此时的我们会发现一个很有趣的性质。
即 s_r\oplus s_{l-1}=a_l \oplus a_{l+1}\,\oplus\,...\oplus\,a_r 。
Why?
因为异或有自反律。
我们以 r=4,l=5 的情况举例：
s_5=a_1 \oplus a_2\,\oplus\,...\oplus\,a_5
s_{4-1}=a_1 \oplus a_2\,\oplus\,a_3
则 s_5\oplus s_3 会抵消 a_1 \oplus a_2\,\oplus\,a_3 。
就能得到 s_5\oplus s_3=a_4\oplus a_5 。
思路梳理
先做一遍前缀异或和。
再枚举 1 到 n-1 ，打擂台求出最大最小值。
每次结果=(s_i+a_{i+1})\oplus s_n\oplus s_i+1
代码实现
核心代码：
for(long long i=1;i<n;i++){
maxx=max(maxx,(s[i]+a[i+1])^(s[n]^s[i+1]));
minn=min(minn,(s[i]+a[i+1])^(s[n]^s[i+1]));
}