Task : Xor(1 <= i <= j <= n) (a[i] + a[j])

Subtask1

O(N^2) : Brute

Subtask2

O(Vmax^2) : For every value x we count the number of its occurrences ( ap[x] ) in the given array. Now we take two values a <= b and we will have two cases :

• if a < b and every value occurs an odd number of times our answer will be updated with (a + b)

• if a = b the number of pairs (1 <= p <= q <= n and val[p] = val[q] = a) will be 1 + 2 + ... + ap[a]. If this number is odd the answer will be updated with (a + b)

Subtask3

O(N logN logVmax) : We will fix a bit , let call it B. We will get an array x i.e. ~x[i] = val[i] % 2^{B+1}~ . We will sort this array x. If we get two values x[p] and x[q] , there will be 4 cases, more precisely, (x[p] + x[q]) will belong to an interval amongst the following ones : \(I_1 = [0... 2^B – 1]\) , ~I_2 = [2^B ... 2 * 2^B - 1]~ , \(I_3 = [2 * 2^B ... 3 * 2^B – 1]\) , \(I_4 = [3 * 2^B ... 4 * 2^B – 1]\). If the sum is in the second or in the fourth, the sum contains the bit B. For every x[pos] we will use binary search to find three indices p1 , p2 , p3, meaning that

\(1 <= i < p1 , x[i] + x[pos] ε I_1 ;\)

\(p1 <= i < p2 , x[i] + x[pos] ε I_2 ;\)

\(p2 <= i < p3 , x[i] + x[pos] ε I_3 ;\)

\(p3 <= i <= n , x[i] + x[pos] ε I_4\)

If p2 – p1 + n + 1 – p3 is odd we will update the answer with ~2^B~ .

Subtask 4

O(N * logVmax) : It is the same idea like the previos one. The two essential observations are :

1. If we are at a bit B + 1, we can pass easily at bit B. This step involves that ~x[i] < 2^{B+2}~ We will split x in two parts. For every ~1 <= i <= K~ , ~x[i] < 2^{B+1}~ and if ~K < i <= n~ , ~x[i] >= 2^{B+1}~ . We will decrease every ~x[i] >= 2^{B+1}~ by ~2^{B+1}~ . These two parts are now sorted and we will merge them in O(n), resulting necessary x.

2. Now, for every position pos, we will update indices p1 , p2 , p3 advancing them from pos – 1 (two pointers trick).