Proficient.
Put your skills to the test.

Problem summary

Count nonempty contiguous subarrays whose bitwise XOR equals zero.

Constraints

1 ≤ N ≤ 500000; 0 ≤ a[i] ≤ 10^9.

Worked example

An independently prepared example for this explanation.

4
1 1 5 4

2

Solution analysis

1. Build prefix XORs P[0]=0 and P[i+1]=P[i] XOR a[i]. XOR cancels repeated operands, so the XOR of a[l..r] is P[l] XOR P[r+1]. It is zero exactly when these two prefix values are equal.
2. Sort the N+1 prefix values. A run of f identical values contributes f*(f−1)/2 pairs. Each pair selects two different prefix positions, which determine one nonempty subarray.
3. For 1,1,5,4 the prefixes are 0,1,0,5,1. Values 0 and 1 each occur twice, giving one pair each. These correspond to subarrays [1,1] and [1,5,4].

Why it works

The prefix cancellation identity gives a bijection between zero-XOR subarrays and unordered pairs of equal prefix values. Sorting groups exactly those equal values, and choosing two positions from each group counts each subarray once.

Watch out. Include the empty prefix P[0]. Count pairs rather than occurrences, and use 64-bit arithmetic for f*(f−1)/2.

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
// Algorithm: Build prefix XORs P[0]=0 and P[i+1]=P[i] XOR a[i].
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int>prefix(n+1,0);
    for(int i=0;i<n;++i){
        int value;
        cin>>value;
        prefix[i+1]=prefix[i]^value;
    }
    sort(prefix.begin(),prefix.end());
    long long answer=0;
    for(int start=0;start<=n;){
        int end=start+1;
        while(end<=n&&prefix[end]==prefix[start]){
            ++end;
        }
        long long frequency=end-start;
        answer+=frequency*(frequency-1)/2;
        start=end;
    }
    cout<<answer<<'\n';
}