Harbour.Space 21-22 Problem H
https://codeforces.com/contest/1553/problem/H
Довольно простая задача, в которой мое решение отличается от авторского.
Писал виртуалку, во время нее задачу не решил. Сегодня решил с чистой головой подумать о ней, и придумал за минут 15 :) Задача на самом деле очень простая, только выглядит сложно, да и она еще и под номером H. В ней есть два подхода, расскажу сначала мой, а потом авторский.
Здесь просто мне захотелось не для x смотреть хорошие пары чисел, а для чисел смотреть им пару и при каких x они будут оптимальными. Тогда хотелось для какого-то a[i] пойти по битам вверх (b 0...k-1), и тогда понятно, что если __lg(a[i] ^ a[j]) = b, то надо взять минимальное a[j] если в a[i] бит b выключен, и максимальное иначе (т.е. если a[j] > a[i], то очевидно хочется взять минимальное a[j], иначе максимальное).
Дальше из этого можно дойти до полного решения. Идти по битам снизу вверх, перебирать x и говорить, что рассмотрим a[i] и a[j], что у них с x совпадают все биты кроме b наименьших, и на каждом ходу брать max число такое, у которого b не будет включен при ксоре c x, и min такое, у которого будет включен. Это делается довольно простой dp-шкой снизу вверх.
Короткий код: https://codeforces.com/contest/1553/submission/209112880
Более длинный, но, кажется, более понятный: https://codeforces.com/contest/1553/submission/209109263
Теперь к авторскому решению. В нем они решили хранить структуру, в которой хотели бы поддерживать ответ. Построим что-то в роде ДО, и просто в каждой вершине храним минимальное x, максимальное x и ответ. Тогда t[x].ans = min(t[l].ans, t[r].ans, t[r].mn - t[l].mx).
Теперь давайте будем идти для x от 0 до 2**k - 1, перестраивать нашу структуру и узнавать ответ.
Тогда если у нас пришел новый x, у которого 0-й бит поменялся, то нам надо перестроить родителей листов (теперь у них дети поменялись местами), а так же обновить ответы для всех всех всех вершин.
А если поменялся (k-1)-й бит, то надо перестроить только корень (у него поменяются дети местами). Если более формально, то чтобы поменять (k-i)-й бит, нам надо перестроить все вершины на глубине < i, то есть делать мы это будем примерно за O(2**i).
Тут мы можем заметить, что идти с x от 0 до 2**k - 1 не очень выгодно, нулевой бит будет меняться очень часто, а он самый трудозатратный. Тогда давайте просто сначала рассмотрим числа, у которых 0-й бит выключен, а затем включен, потом те, у котрых 1-й бит выключен, а затем включен, ... Это мы будем делать рекурсией, в итоге 0-й (самый тяжелый бит) поменяется всего 1 раз, а (k-1)-й (самый легкий) поменяется много раз. Делать это будем рекурсией.
Код: https://codeforces.com/contest/1553/submission/209115383