Здравствуйте! Есть q запросов вида x_i к массиву a из n элементов — целых 32-битных беззнаковых чисел. Каждый запрос — побитовый xor всех элементов массива с элементом x_i. После каждого запроса нужно выводить максимум на всем массиве. Ограничения на n и q порядка 2·10⁵.

Я помню задачу с нахождением суммы на отрезке и применением xor на отрезке — там она решалась построением 32 деревьев отрезков под каждый разряд, а сумма формировалась как сумма элементов по модулю 2 умноженная на соответствующую степень двойки, которой соответствует дерево отрезков.

В этой же задаче отрезок не произвольный, а фиксированный — весь массив. Как решать эту задачу?

Приведу изначальную формулировку, может она легче: есть два массива a и b длины n, нужно найти максимальное значение среди всех попарных xor элементов пар (a[i], b[j]) элементов массивов.

Ну и еще более изначальную: есть корневое дерево с n вершинами и n-1 ребрами. На ребрах записаны некоторые целые числа, а на каждом ребре одно число. Нужно выбрать две различные вершины дерева u и v такие, что выписав все числа на пути от вершины u до корня и от вершины v до корня, а затем выполнить операцию xor для всех выписанных элементов, итоговое значение было бы максимальным среди всех пар (u,v). В ответ выдать это значение. Задача

UPD: Сдал задачу при помощи сортировки + неявного бора + бинарного поиска за O(n * log(n) * WORD_WIDTH). Код к задаче, исходная формулировка оказалась легче — не пришлось изменять элементы массива.