Здравствуйте! Есть 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). В ответ выдать это значение. Задача
UPD: Сдал задачу при помощи сортировки + неявного бора + бинарного поиска за O(n * log(n) * WORD_WIDTH). Код к задаче, исходная формулировка оказалась легче — не пришлось изменять элементы массива.
Бор :)
А как за логарифм от количества чисел все пересчитывать? В худшем случае, листьев столько же, сколько и элементов в массиве, существует какой-то хитрый способ?
UPD1: Похоже, я начинаю догадываться, если, в каком-то разряде числа x стоит 1, то нам нужно переподвесить все ветки на этом уровне, то есть, сделать swap дочерних элементов. Но их все равно получается очень много. Для каждого уровня хранить дополнительное значение — был ли swap или нет, обрабатывать только тогда, когда происходит спуск к самой правой ветке?
UPD2: Можно в таком случае завести 32 дерева отрезков под каждый уровень, если 1 в разряде — то на всем уровне нужно обменять ссылки на дочерние элементы местами, но нужно только отметить, что обмен должен быть. Когда мы начинаем спускаться к самой правой ветке, то мы посетим не больше 32 вершин на пути, необходимо проверять, если ли отметка, и снять ее, если есть, обменяв ссылки на дочерние элементы местами, так?
UPD3: 32 не нужно, хватит и одного дерева отрезков. Асимптотика O(n * log(n) * WORD_WIDTH). Добавил ссылку на задачу, ее сдало всего три человека. Попробую сдать, спасибо за идею!
Пересчитывать всё можно за O(1). Заметим, что xor — ассоциативная операция, то есть (ai^xi)^xi + 1 = ai^(xi^xi + 1). Значит, на i-м шаге надо находить maxj = 1... n(aj^x), где x = x1^x2^... ^xi. Мы свели задачу к тому, что надо находить ответы на кучу запросов, описанных выше, не меняя массив. Причём в запросах меняется только число x, который я и буду пересчитывать.
Как это сделать? Это уже тривиально. Заводим цифровой бор для наших элементов. Затем спускаемся по нему с оглядкой на текущий x — если на очередном месте в нём стоит 1, то следует пытаться спуститься по ребру, соответствующему 0, иначе наоборот. Под <<пытаться спуститься>> я подразумеваю пойти по соответствующему ребру, если в соответствующем поддереве есть хотя бы одна терминальная вершина.
Итого, я научился на запрос отвечать за O(1) + O(log(max(a))), где O(1) — пересчёт x, O(log(max(a))) — спуск по дереву.
Сдал задачу при помощи сортировки + неявного бора + бинарного поиска Код к задаче, исходная формулировка оказалась легче — не пришлось изменять элементы массива.