题目描述
There is an integer sequence A of length N.
Find the number of the pairs of integers l and r (1≤l≤r≤N) that satisfy the following condition:
Al xor Al+1 xor … xor Ar=Al + Al+1 + … + Ar
Here, xor denotes the bitwise exclusive OR.
Definition of XOR
Constraints
1≤N≤2×105
0≤Ai<220
All values in input are integers.
输入
Input is given from Standard Input in the following format:
N
A1 A2 … AN
输出
Print the number of the pairs of integers l and r (1≤l≤r≤N) that satisfy the condition.
样例输入 Copy
4
2 5 4 6
样例输出 Copy
5
提示
(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition. (l,r)=(1,2) also satisfies the condition, since A1 xor A2=A1 + A2=7. There are no other pairs that satisfy the condition, so the answer is 5.
求出有多少个区间(l,r) 满足区间的异或和等于区间和
区间异或和 与 区间和 在处理完前缀之后，会满足：
a[l] + a[l+1] + .... == sum[r] - sum[l-1] a[l] ^ a[l+1] ^ ... == xorSum[r] ^ xorSum[l-1]
对于一个左端点l和右端点r，如果说l->r之间满足区间异或和等于区间和，那么说从l -> r-1也是满足的，所以说此时对答案的贡献便是区间的长度r - l + 1,我们只需要找满足情况的最右端的端点就好，然后统计对答案的贡献
区间的个数会爆掉int，记得开long long
二分的时候直接将l or r 当成区间的端点可能不太准确，需要将每次的mid用一个变量记录下来
二分代码：
typedef int itn; int n,k; ll a[maxn]; ll s[maxn]; ll sxor[maxn]; int main() { n = read; for(int i=1;i<=n;i++) a[i] = read; for(int i=1;i<=n;i++){ s[i] = s[i-1] + a[i]; sxor[i] = sxor[i-1] ^ a[i]; } ll ans = 0; for(int i=1;i<=n;i++){ int l = i,r = n; int t = 0; while(l <= r){ int md = (r + l) >> 1; if(s[md] - s[i-1] == (sxor[md] ^ sxor[i-1])){ l = md + 1; t = md; } else r = md - 1; } ans += t - i + 1; } cout << ans << endl; return 0; }
尺取代码：
typedef int itn; int n,k; ll a[maxn]; ll s[maxn]; ll sxor[maxn]; int main() { n = read; for(int i=1;i<=n;i++) a[i] = read; ll ans = 0; for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i],sxor[i] = sxor[i-1] ^ a[i]; ll sum = 0; int l = 1; for(int i=1;i<=n;i++){ while((sum^a[i]) != sum + a[i]){ sum ^= a[l]; l ++; } sum ^= a[i]; ans += i - l + 1; } cout << ans <<endl; return 0; } /************************************************************** Problem: 7731 Language: C++ Result: 正确 Time:28 ms Memory:25468 kb ****************************************************************/
