3741. Subarray with maximum XOR

Given an array of integers. Find the subarray with maximum XOR.

Input. The first line contains the size of array n (n ≤ 10⁵). Second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10¹⁸).

Output. Print such l and r for which the value a_l xor a_l+1 xor ... xor a_r is maximum among all possible subarrays [l…r] (1 ≤ l ≤ r ≤ n). Then in the same line print the value of maximum XOR.

Sample input	Sample output
7 2 8 12 4 9 2 3	4 6 15

SOLUTION

trie

Algorithm analysis

Consider the following series of numbers:

b₀ = 0,

b₁ = a₁,

b₂ = a₁ xor a₂,

...,

b_n = a₁ xor a₂ xor … xor a_n

The numbers b₀, b₁, b₂, ..., b_n will be sequentially inserted into the binary trie. Let b₀, b₁, b₂, ..., b_i are already in the trie. Find a number b_k (k < i) such that b_k xor b_i is maximal. Given that b_k xor b_i = a_k+1 xor … xor a_i, with this operation we are looking for a subarray with the maximum XOR that ends in a_i. Among all such maxima, we look for the largest one, which is the answer.

Algorithm realization

Declare a binary trie, the sons of the trie vertices correspond to bits 0 and 1. The size of the trie is stored in TrieSize variable.

#define MAX 100001

int trie[MAX * 60][2];

long long b[MAX], mx;

int num[MAX * 60], TrieSize;

The function Insert inserts a number x = b[pos] into the trie.

void Insert(int pos)

{

int v = 0;

long long x = b[pos];

Inserting a number into a trie starts with the high bits.

for (int i = 62; i >= 0; i--)

{

The variable bit contains the i-th bit of number x.

int bit = x & (1LL << i) ? 1 : 0;

If there is no path along the bit in the trie, we create a new vertex.

if (trie[v][bit] == -1)

trie[v][bit] = TrieSize++;

Move further along the trie.

v = trie[v][bit];

}

Vertex v is final for the number x = b[pos]. Store in num[v] the index pos of array b.

num[v] = pos;

}

The function Find returns the index pos of array b for which x xor b_pos is maximum.

int Find(long long x)

{

int i, v = 0;

for (i = 62; i >= 0; i--)

{

Move in the trie along the bits that are reverse to the binary representation of the number x.

int bit = x & (1LL << i) ? 0 : 1; // reverese bit

If the movement along the trie is impossible, move along another bit.

if (trie[v][bit] == -1) bit ^= 1;

v = trie[v][bit];

}

Return the index pos of array b, that corresponds to the vertex v of the trie.

return num[v];

}

The main part of the program. Read the input data. Initially trie contains one vertex (TrieSize = 1). Initialize the trie and num arrays.

scanf("%d", &n);

TrieSize = 1;

memset(trie, -1, sizeof(trie));

memset(num, -1, sizeof(num));

Insert to the trie b₀ = 0. Compute in the variable mx, the maximum XOR value on subarray.

b[0] = 0;

Insert(0);

mx = 0;

Insert the rest of the sequence b₁, b₂, ..., b_n into the trie.

for (i = 1; i <= n; i++)

{

Read the value of a_i = val.

scanf("%lld", &val);

Compute b_i = b_i-1 xor a_i.

b[i] = b[i - 1] ^ val;

Insert the value b_i into the trie.

Insert(i);

Find such value of k, that b_k xor b_i is maximum. Subarray with maximum XOR that ends at position i starts at k + 1. Not that b_k xor b_i = a_k+1 xor … xor a_i.

k = Find(b[i]);

Among all the values a_k+1 xor … xor a_i (i = 1, 2, …, n) find maximum.

if ((b[k] ^ b[i]) > mx)

{

mx = b[k] ^ b[i];

l = k + 1;

r = i;

}

}

Print the boundaries l and r of desired subarray and XOR value on it.

printf("%d %d %lld\n", l, r, mx);