E. Beautiful Subarrays
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
One day, ZS the Coder wrote down an array of integers a with elements a1, a2, ..., an.
A subarray of the array a is a sequence al, al + 1, ..., ar for some integers (l, r) such that 1 ≤ l ≤ r ≤ n. ZS the Coder thinks that a subarray of a is beautiful if the bitwise xor of all the elements in the subarray is at least k.
Help ZS the Coder find the number of beautiful subarrays of a!
Input
The first line contains two integers n and k (1 ≤ n ≤ 106, 1 ≤ k ≤ 109) — the number of elements in the array a and the value of the parameter k.
The second line contains n integers ai (0 ≤ ai ≤ 109) — the elements of the array a.
Output
Print the only integer c — the number of beautiful subarrays of the array a.
Examples
input
3 1 1 2 3
output
5
input
3 2 1 2 3
output
3
input
3 3 1 2 3
output
2
Explanation
XOR on subarrays always hint us towards tries.
The problem was suggested by Zi Song Yeoh zscoder.
The sign 
is used for the binary operation for bitwise exclusive or.
is used for the binary operation for bitwise exclusive or.
Let si be the xor of the first i elements on the prefix of a. Then the interval (i, j] is beautiful if 
. Let's iterate over j from 1 ton and consider the values sj as the binary strings. On each iteration we should increase the answer by the value zj — the number of numbers si (i < j) so . To do that we can use the trie data structure. Let's store in the trie all the values si for i < j. Besides the structure of the trie we should also store in each vertex the number of leaves in the subtree of that vertex (it can be easily done during adding of each binary string). To calculate the value zj let's go down by the trie from the root. Let's accumulate the value curequals to the xor of the prefix of the value sj with the already passed in the trie path. Let the current bit in sj be equal to b and i be the depth of the current vertex in the trie. If the number cur + 2i ≥ k then we can increase zj by the number of leaves in vertex 
, because all the leaves in the subtree of tha vertex correspond to the values si that for sure gives . After that we should go down in the subtree b. Otherwise if cur + 2i < k then we should simply go down to the subtree 
and recalculate the valuecur = cur + 2i.
. Let's iterate over j from 1 ton and consider the values sj as the binary strings. On each iteration we should increase the answer by the value zj — the number of numbers si (i < j) so . To do that we can use the trie data structure. Let's store in the trie all the values si for i < j. Besides the structure of the trie we should also store in each vertex the number of leaves in the subtree of that vertex (it can be easily done during adding of each binary string). To calculate the value zj let's go down by the trie from the root. Let's accumulate the value curequals to the xor of the prefix of the value sj with the already passed in the trie path. Let the current bit in sj be equal to b and i be the depth of the current vertex in the trie. If the number cur + 2i ≥ k then we can increase zj by the number of leaves in vertex , because all the leaves in the subtree of tha vertex correspond to the values si that for sure gives . After that we should go down in the subtree b. Otherwise if cur + 2i < k then we should simply go down to the subtree and recalculate the valuecur = cur + 2i.
C++ solution
Comlpexity by the time and the memory: O(nlogX), where X is the maximal xor on the prefixes.
************************************HERE GOES MY CODE **********************************
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
ll a[1000010];
class node
{
public:
node *lt,*rt;
int sub;
node()
{
lt=NULL;
rt=NULL;
sub=0;
}
};
void insert(node *root,ll val)
{
for(int i=32;i>=0;i--)
{
if(val>>i&1)
{
if(root->rt==NULL)
{
root->rt=new node();
}
root=root->rt;
root->sub++;
}
else
{
if(root->lt==NULL)
{
root->lt=new node();
}
root=root->lt;
root->sub++;
}
}
}
ll query(node *root,ll val,ll K)
{
ll ret=0;
for(int i=32;i>=0;i--)
{
int v=val>>i&1;
int k=K>>i&1;
node *temp;
if(v==1 && k==0)
{
temp=root->lt;
if(temp!=NULL)
{
ret+=temp->sub;
// cout<<"ad ledt subtree "<<endl;
}
if(root->rt!=NULL)
{
root=root->rt;
// cout<<"go to rt "<<endl;
}
else
{
//cout<<"direct ret "<<endl;
return ret;
}
}
else if(v==1 && k==1)
{
if(root->lt!=NULL)
{
// cout<<"only option go to lt "<<endl;
root=root->lt;
}
else
{
//cout<<"return ret "<<endl;
return ret;
}
}
else if(v==0 && k==0)
{
temp=root->rt;
if(temp!=NULL)
{
//cout<<"add values on rt subtree "<<endl;
ret+=temp->sub;
}
if(root->lt!=NULL)
{
//cout<<"go to lefct "<<endl;
root=root->lt;
}
else
{
//cout<<"else return ret "<<endl;
return ret;
}
}
else
{
if(root->rt!=NULL)
{
// cout<<"tru and go to rt "<<endl;
root=root->rt;
}
else
{ // cout<<"elset return ret "<<endl;
return ret;
}
}
if(i==0)
{
ret+=root->sub;
}
}
return ret;
}
int main()
{
int n;
cin>>n;
ll k;
cin>>k;
node *root=new node();
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
}
insert(root,0);
// cout<<" inserted "<<endl;
int pre=0;
ll ans=0;
for(int i=1;i<=n;i++)
{
pre=pre^a[i];
ans+=query(root,pre,k);
insert(root,pre);
}
cout<<ans<<endl;
}
