AC代码

https://codeforces.com/contest/1732/submission/183796249

题意：

给你一个整数数组a1，a2，…，an。

数组子段[1，r]的成本，1≤l≤r≤n、 是值f（l，r）=sum（l，r）−xor（l，r），

其中sum（l，r）=a_l+a_(l+1)+…+a_r，

xor（1，r）=al⊕al+1⊕…⊕ar (⊕ 代表按位XOR）。

您将有q个查询。每个查询由一对数字Li，Ri给出，其中1≤Li≤Ri ≤n、

你需要找到子段[l，r]，Li≤l ≤r≤Ri，具有最大值 f（l，r）。

如果有几个答案，那么需要在其中找到长度最小的子段，即最小值 r−l+1。

题解：

双指针搜素

考察f(l,r)=sum(l,r)−xor(l,r) 的性质。

假如一个数 x，对 sum 的贡献为 x，而对 xor 的贡献小于等于 x，因为可能异或和中 有相同的bit位。

显而易见的结论是假如不要求区间长度最小，[L,R] 就是最终的答案，所以 最大值已经确定为 f(L,R)，

只需要找长度最小的区间满足 f(l,r)=f(L,R) 。