C++课后习题训练记录Day109
1.练习项目：
题目描述
欢迎来到异或王国，这是一个特殊的王国，对于一个数组它的价值并非所有数相加，而是所有数异或得到的值。
当然对于某些神奇的数组来说值可能是一样的，给定一个长度为 n 的数组 a ，请问有多少个子数组是神奇数组。
换句话说，在数组 a 中存在多少对下标 l 和 r(1≤l≤r≤n) 满足：al⊕al+1⊕...⊕ar=al+al+1+...+ar
输入格式
第一行输入一个整数 n ，表示数组 a 的长度。
第二行输入 n 个整数，表示数组 a 的值。
数据保证 1≤n≤2×10^5，0≤ai<2^20。
输出格式
输出一个整数表示答案。
2.选择课程
在蓝桥云课中选择课程《16届蓝桥杯省赛无忧班（C&C++ 组）4期》，选择第二章“基础算法”编程39并开始练习。
3.开始练习
（1）前缀和：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=2e5+10;
ll a[N];
ll preSum[N],x[N];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
preSum[0]=0;x[0]=0;
for(int i=1;i<=n;i++){
cin>>a[i];
preSum[i]=preSum[i-1]+a[i];
x[i]=(x[i-1]^a[i]);
}
int i=1,j=1;
ll cnt=0;
while(i<=n&&j<=n){
if((x[i-1]^x[j])==(preSum[j]-preSum[i-1])){
cnt+=j-i+1;
j++;
}
else i++;
}
cout<<cnt<<'\n';
return 0;
}
（2）双指针：
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n;cin>>n;
vector<int>a(n);
for(int i=0;i<n;i++){
cin>>a[i];
}
int l=0,r=0,res=0;
ll ans=0;
while(l<n){
while(r<n&&((res^a[r])==(res+a[r]))){
res^=a[r];
r++;
}
ans+=r-l;
res^=a[l];
l++;
}
cout<<ans<<'\n';
return 0;
}
（2）检验结果
对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。
（3）练习心得：
解题思路
异或运算，也称之为不进位加法，也就是说两个二进制数相加时如果没有产生进位，那么此时两个数异或的值等于相加的值，该性质推广到多个数也成立。所以对于一个神奇数组来说，每一个比特位它都最多只有一个数可以在该位为 1 ，因为对于二进制来说逢二进一，如果某个比特位不止一个数在该位为 1 ，那么这个数组在相加时就会产生进位。
根据这个性质，我们只需要枚举每个数作为数组的左边界 l，看最多有多少个右边界 r 使得区间 [l,r] 是满足性质的。我们考虑如何去求 r ，不难发现这其实是具有二段性的（
- 当区间内所有数的二进制位互不重叠时，加入一个新数，如果该数的二进制位与当前区间已有位没有冲突，则新区间仍然合法；一旦某个新数引入了与已有位重叠的位，就会产生进位冲突，导致异或不等于和。
- 由于左端点固定，冲突一旦出现就无法通过继续向右添加数来消除（因为冲突的位会一直存在），因此之后的所有右端点都不再合法。
），假设区间 [l,r] 是满足条件的，显然区间 [l,l+1]，[l,l+2]...[l,r−1] 也一定满足条件，而 r 变大时并不一定满足，所以我们可以二分求得 r ，但在判断时需要求区间和和区间异或值，这需要维护一个前缀和数组和前缀异或数组帮助我们查询，有点麻烦，当然这个做法复杂度为 O(nlogn) 是完全可过的。
考虑更好的做法，当我们从左向右枚举 l 时，不难发现 r 是具有单调性的（
- 我们始终保证当前窗口
[l, r-1]是合法的（即窗口内所有数的异或等于和）。 - 当
l增加时，我们从窗口中移除左边的元素a[l]。移除元素不会破坏窗口的合法性，因为移除只会减少二进制位的冲突（如果之前有冲突，移除后可能消除冲突），但不会引入新的冲突。因此，原本合法的窗口在移除左边元素后依然合法，而且有可能使得右指针r能够继续向右扩展（因为冲突被消除了）。 - 由于
r之前已经尽可能向右移动到了当前l下的最大合法位置，当l增加后，这个最大合法位置只可能不变或更大，绝不会变小。所以r不需要向左移动，只需要继续向右尝试即可。
），它只会向右移动，所以我们使用双指针来维护区间，替换掉上面的二分做法，这是很经典的应用。这样做不仅代码量变小了，复杂度也降为了 O(n) 。
注意每段代码末尾的分号是否存在，如不存在则需即使补充；输入法是否切换为英语模式；语法是否错误。
