3741. Подмассив с максимальным XOR

Задан массив целых чисел. Найдите подмассив с максимальным XOR.

Вход. Первая строка содержит размер массива n (n ≤ 10⁵). Вторая строка содержит n целых чисел a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10¹⁸).

Выход. Выведите такие l и r, для которых a_l xor a_l+1 xor ... xor a_r принимает наибольшее значение среди всех возможных подмассивов [l .. r] (1 ≤ l ≤ r ≤ n). Дальше в этой же строке выведите значение максимального XOR.

Пример входа	Пример выхода
7 2 8 12 4 9 2 3	4 6 15

РЕШЕНИЕ

бор

Анализ алгоритма

Рассмотрим следующий ряд чисел:

b₀ = 0,

b₁ = a₁,

b₂ = a₁ xor a₂,

...,

b_n = a₁ xor a₂ xor … xor a_n

Числа b₀, b₁, b₂, ..., b_n будем последовательно заносить в бинарный бор. Пусть b₀, b₁, b₂, ..., b_i уже находятся в боре. Найдем такое число b_k (k < i), что b_k xor b_i максимально. Учитывая что b_k xor b_i = a_k+1 xor … xor a_i, этой операцией мы ищем подмассив с максимальным XOR, который заканчивается в a_i. Среди всех таких максимумов ищем наибольший, который и является ответом.

Реализация алгоритма

Объявим бинарный бор trie, сыновья вершин бора соответствуют битам 0 и 1. В переменной TrieSize храним его размер.

#define MAX 100001

int trie[MAX * 60][2];

long long b[MAX], mx;

int num[MAX * 60], TrieSize;

Функция Insert вставляет число x = b[pos] в бор.

void Insert(int pos)

{

int v = 0;

long long x = b[pos];

Вставка числа в бор начинается со старших битов.

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

{

Переменная bit содержит i-ый бит числа x.

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

Если пути по биту bit в боре нет, то создаем новую вершину.

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

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

Двигаемся по бору дальше.

v = trie[v][bit];

}

Вершина v – конечная для числа x = b[pos]. Сохраним в num[v] индекс pos в массиве b.

num[v] = pos;

}

Функция Find возвращает индекс pos массива b, для которого x xor b_pos максимально.

int Find(long long x)

{

int i, v = 0;

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

{

Двигаемся по бору по битам, реверсным к двоичному представлению числа x.

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

Если движение по бору невозможно, двигаемся по другому биту.

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

v = trie[v][bit];

}

Возвращаем индекс pos массива b, соответствующий вершине бора v.

return num[v];

}

Основная часть программы. Читаем входные данные. Изначально бор содержит одну вершину (TrieSize = 1). Инициализируем массивы trie и num.

scanf("%d", &n);

TrieSize = 1;

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

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

Вставим в бор b₀ = 0. В переменной mx вычисляем максимальное значение XOR на подмассиве.

b[0] = 0;

Insert(0);

mx = 0;

Вставляем остальные числа последовательности b₁, b₂, ..., b_n в бор.

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

{

Читаем значение a_i = val.

scanf("%lld", &val);

Вычисляем b_i = b_i-1 xor a_i.

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

Вставляем значение b_i в бор.

Insert(i);

Находим такое k, что b_k xor b_i максимально. Подмассив с максимальным XOR, который заканчивается в позиции i, начинается в k + 1. Отметим, что b_k xor b_i = a_k+1 xor … xor a_i.

k = Find(b[i]);

Среди всех значений a_k+1 xor … xor a_i (i = 1, 2, …, n) находим наибольшее.

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

{

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

l = k + 1;

r = i;

}

}

Выводим границы l и r искомого подмассива и значение XOR на нем.

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