XOR элементов массива с заданным числом + максимум в массиве

Revision ru4, by dmkz, 2018-07-02 04:37:43

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

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

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

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

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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru6 Russian dmkz 2018-07-02 05:49:33 6
ru5 Russian dmkz 2018-07-02 05:40:46 297
ru4 Russian dmkz 2018-07-02 04:37:43 106
ru3 Russian dmkz 2018-07-02 02:06:10 635
ru2 Russian dmkz 2018-07-02 01:51:18 52
ru1 Russian dmkz 2018-07-02 01:50:45 746 Первая редакция (опубликовано)