题目描述
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
****************************************************************/
