**Algorithm:**

**1.**If you want to get XOR of array elements in range [I, J], you can do it by taking the XOR of [1, I-1] with XOR[1, J]. (How does this solve the problem? - See next points.)

**2.**Make a trie of the bit representation of the XOR of elements.

Suppose the array is: 4, 1, 3, 2, 7. and k = 2.

**Binary Rep. XOR K=2 Bin = 010**

**4**100

**100**

**1**001

**101**

**3**011

**110**

**2**010

**100 <-- (example case below)**

**7**111

**011**

For each element of the array,

**1.**Insert the value 0 to the Trie (test for cases like when there is only one element present and is less than k).

**2.**Find it's XOR with the previous value (0 if first). Now find how many subarrays are present whose XOR is less than k. How? ->

Consider the case when you've inserted XOR with element 3 and considering the element 2 to pass its XOR to query.

Now k = 2 its binary rep. is 010. Now you take this representation of k and the current XOR value's (for 2 = 100) binary representation to guide your search through the trie.

k1 = 0. Now above the value 2 in the array, all those XORs whose bit at index = 1 is = 1, when taken XOR with "1"00 will give a value 0. These XORs are the ones who may be less than or equal to the value k. Those XOR values who have a 0 in the first bit when taken XOR with "1"00 will give 1 which means that all those XORs are greater than k. Here's the full detail-

**Check the first bits below:-**

**100 ^ 100 -> 000**= (0 in the first position). Can be less than k. This represents the XOR of 1,3,2 as you are taking xor of 4,1,3,2 with 4 so you get

**xor of 1,3,2.**

**100 ^ 101 -> 001**= (0 in the first position again). Can be less than k. This represents the XOR of 4,1 with XOR of 4,1,3,2 =

**XOR of 3, 2.**

**100 ^ 110 -> 010**= (0 in the first position again). Can be less than k. This represents the XOR of 4,1,3 with XOR of 4,1,3,2 =

**XOR of 2.**

**100 ^ 000**(the first 0 we inserted in the trie) -> represents the

**XOR of 4,1,3,2.**

So all the possible sequences ending at 2 have been considered. A trie thus helps to get the answer fast.

3. Do this until the last element of the array has been considered.

**Code (C++):**

#include <stdio.h> #define MAX 200000 struct node{ int nL, nR; int leftIndex, rightIndex; node(){ nL = 0; nR = 0; leftIndex=-1; rightIndex=-1; } }; int gIndex=0; void insert(int value, int index, int depth, node *tree){ for(int i = depth-1;i>=0;--i){ int bit = value>>i & 1; if(bit){ tree[index].nR++; if(tree[index].rightIndex==-1){ tree[index].rightIndex = ++gIndex; index = gIndex; }else index = tree[index].rightIndex; }else{ tree[index].nL++; if(tree[index].leftIndex==-1){ tree[index].leftIndex = ++gIndex; index = gIndex; }else index = tree[index].leftIndex; } } } int query(int value, int compare, int index, int depth, node* tree){ int ans=0; for(int i=depth-1;i>=0;--i){ int vBit = value>>i & 1; int cBit = compare>>i & 1; if(cBit){ if(vBit){ans += tree[index].nR; index = tree[index].leftIndex;} else{ans += tree[index].nL; index = tree[index].rightIndex;} }else{ if(vBit) index = tree[index].rightIndex; else index = tree[index].leftIndex; } if(index==-1)break; } return ans; } int main(){ int d; scanf("%d", &d); while(d--){ node tree[MAX]; gIndex=0; int n, k; scanf(" %d %d", &n, &k); int XOR = 0, t=0; long long ans=0; insert(0, 0, 20, tree); while(n--){ scanf(" %d", &t); XOR = XOR ^ t;ans+= query(XOR, k, 0, 20, tree); insert(XOR, 0, 20, tree); } printf("%lld\n", ans); } }

Why is 20 being chosen as the depth always?

ReplyDelete