Обозначим для двоичных чисел четыре побитовые логические операции: побитовое И, ИЛИ, исключающее ИЛИ и НЕ.
В основном нас, конечно, интересуют последние три, так как они определены на двух операндах.
Одно из главных свойств двоичной арифметики - \( 2^k > 2^{k-1} + 2^{k-2} ... +2^0 \), что позволяет иметь смысл многим жадным алгоритмам.
Пускай у нас есть множество чисел \(S\). Определим \(or(S)\) как побитовое ИЛИ всех чисел множества. Очевидно, что добавив число к множеству \(or(S)\) не уменьшится.
Кроме того, \( max(S) * 2 > or(S) \), так как мы только добавим некоторые биты к максимуму, то есть число увеличится на значение, меньшее старшему биту.
Рассмотрим префикс массива \(a\) целых неотрицательных чисел. Значение с увеличением префикса либо не изменяется, либо возрастает (по первому свойству). Более того, будет не более \( \log{ max(a_i)} \) изменений (потому что каждое изменение - добавление бита, которых всего \( \log{n} \) ).
По аналогии обозначим функцию \(and(S)\) - побитовое И множества. Аналогично, добавление числа в множество не увеличивает значение функции.
Также префикс будет меняться \( \log{max(a_i)} \) раз и невозрастать.
Одно из важных свойств - \( x \oplus x = 0\). Также заметим, что \( x \oplus y = z \) равносильно \( y = z \oplus x\).
Реализация за \( O(\log{n}) \) или \(O(1)\) тривиальна с помощью структур на отрезках. Давайте решим за \(O( \log{C}) \) на запрос. Насчитаем для каждого бита префиксные суммы. Тогда если на отрезке присутствует хоть один бит - значит он будет присутствовать и в ответе.
Аналогично ИЛИ. Только надо проверить что количество битов равно длине отрезка, чтобы в ответе поставить данный бит.
Насчитаем префиксные XOR-суммы. Тогда XOR на отрезке \([l;r]\) равен \( pref_r \oplus pref_{l-1} \).
Небезынтересен тот факт, что XOR на путях (XOR всех величин ребер на простом пути между вершинами) дерева очень легко обрабатывается: насчитаем префиксные XOR-суммы на путях от корня до вершин. Ответом возьмем XOR этих двух значений вершин. Ребра на пути мы учтем правильно, а ребра от LCA до корня мы учтем дважды, но по первому свойству они занулятся.
Максимальное ИЛИ массива - ИЛИ всех значений массива. Другая задача - наименьшее по размеру множество, чье ИЛИ равно максимальному, решается динамическим программированием.
Тоже что и И всех значений.
На самом деле существует тривиальное решение этой задачи: давайте отсортируем числа и переберем все пары соседних элементов. Это работает, потому что у соседних чисел префикс максимально совпадает (при операции XOR они занулятся).
Пусть дан массив \(a\) длины \(n\), необходимо найти максимальное \(a_i \oplus a_j\).
Будем поддерживать битовый бор. Пускай обрабатываем очередное число \(x\). Нам нужно найти максимальный XOR с теми значениями, что мы добавили. Пускай очередной бит равен \(0\). Тогда, чтобы ответ был максимален, мы должны туда, чтобы \(XOR\) был равен \(1\), если это возможно. Напротив, если текущий бит равен \(1\) мы должны спускаться по ребру \(0\). Если нужное нам ребро отсуствует, то спускаемся по оставшемуся. После спуска у нас получится максимальный XOR, который мы могли получить из уже добавленных чисел. После этого добавим \(x\) в бор.
Давайте построим ответ жадно: от старшего бита к младшему. Пускай мы уже знаем, что ответ имеет какой-то префикс \(x\). Давайте попробуем приписать к префиксу \(1\). Теперь нам надо проверить, существует ли пара чисел, чей XOR имеет такой префикс. Для каждого числа сохраним в таблицу его префикс (первые биты, которые мы рассматриваем). Теперь для каждого числа проверим найдется ли пара ему: проверим, есть ли в таблице префикс, совпадающий с префиксом \(a_i \oplus x\).
Оба решения работают за \( O(n * \log{C} ) \)
Будем конструировать ответ бит за битом (от старшего к младшему). Пускай мы уже знаем, что ответ имеет префикс равный \(x\). Тогда попробуем дописать \(1\) к префиксу. Посмотрим, сколько чисел \(a_i\) имеют такой префикс как подмаску. Если таких чисел не меньше двух, то мы можем дописать \(1\), иначе - нет.