AC代碼

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

題意：

給你一個整數(shù)數(shù)組a1，a2，…，an。

數(shù)組子段[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個查詢。每個查詢由一對數(shù)字Li，Ri給出，其中1≤Li≤Ri ≤n、

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

如果有幾個答案，那么需要在其中找到長度最小的子段，即最小值 r?l+1。

題解：

雙指針?biāo)阉?/p>

考察f(l,r)=sum(l,r)?xor(l,r) 的性質(zhì)。

假如一個數(shù) x，對 sum 的貢獻為 x，而對 xor 的貢獻小于等于 x，因為可能異或和中 有相同的bit位。

顯而易見的結(jié)論是假如不要求區(qū)間長度最小，[L,R] 就是最終的答案，所以 最大值已經(jīng)確定為 f(L,R)，

只需要找長度最小的區(qū)間滿足 f(l,r)=f(L,R) 。