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