Difficulty
Medium
Problem
Solution
We know that xor[1....j] = xor[1...i-1]\oplus xor[i...j]
\Rightarrow xor[1...i-1] = xor[1...j]\oplus xor[i...j]
\Rightarrow xor[1..i-1] = xor[1...j]\oplus 2^p
So on this basis we can say that the number of subarrays ending at j and having xor value equal to 2^p will be equal to the number of i such that i \leq j and xor[1...i-1] = xor[1...j]\oplus 2^p. Keep in mind that for the given constraints, p can be anything from 0 to 10. We can create an array count where count_k basically stores the number of prefix subarrays having xor value equal to k, we will keep updating this as we move our j from 1 to n. Therefore the number of subarrays ending at or before j and having xor value of the form 2^p will be given by \sum_{k=1}^{k\leq j}\sum_{p=0}^{p\leq 10}count[xor[1...k]\oplus 2^p].
Using prefix sum methods we can now easily answer the queries of the first type. The second kind of queries can be also handled in similar way with some minor changes, like now we will move our j from n to 1 and construct our count array also in this order.
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int n,q;
cin>>n>>q;
vector<int>arr(n+1);
vector<int>end(n+1);
vector<int>start(n+1);
vector<int>count_end(1<<11); //count array for the queries of the first kind
vector<int>count_start(1<<11); //count array for the queries of the second kind
for(int i=1; i<=n; i++){
cin>>arr[i];
}
int sum=0;
count_end[0]=1;
for(int i=1; i<=n; i++){
sum=sum^arr[i];
for(int j=0; j<11; j++){
end[i]+=count_end[sum^(1LL<<j)];
}
count_end[sum]++;
}
count_start[0]=1;
sum=0;
for(int i=n; i>=1; i--){
sum=sum^arr[i];
for(int j=0; j<11; j++){
start[i]+=count_start[sum^(1LL<<j)];
}
count_start[sum]++;
}
vector<ll>pf_end(n+1),pf_start(n+1);
for(int i=1; i<=n; i++){
pf_end[i]=pf_end[i-1]+end[i];
}
for(int i=n; i>=1; i--){
if(i==n)
pf_start[i]=start[i];
else
pf_start[i]=pf_start[i+1]+start[i];
}
while(q--)
{
int type,pos;
cin>>type>>pos;
if(type==1){
cout<<pf_end[pos]<<"\n";
}
else
cout<<pf_start[pos]<<"\n";
}
return 0;
}