Разбор задачи «Сигнал дальнего сканера»

Идея задачи

Нам даны два числа l и r. Нужно выбрать такие a и b, что:

• l ≤ a ≤ b ≤ r,
• значение a xor b было максимально возможным.

На первый взгляд может показаться, что нужно как-то перебирать разные пары чисел из отрезка. Но отрезок может быть очень большим, поэтому такой подход сразу не подходит.

Главная мысль задачи связана не с самими числами, а с их двоичной записью.

Напоминание: что делает операция XOR

Операция xor сравнивает биты двух чисел.

• 0 xor 0 = 0
• 0 xor 1 = 1
• 1 xor 0 = 1
• 1 xor 1 = 0

То есть бит результата равен 1 тогда и только тогда, когда соответствующие биты двух чисел различаются.

А значит, чтобы сделать значение a xor b как можно больше, нам особенно важно получить единицы в старших битах, потому что именно они сильнее всего влияют на значение числа.

Ключевое наблюдение

Посмотрим на двоичные записи чисел l и r.

Пока их старшие биты совпадают, у всех чисел внутри отрезка [l, r] эти биты тоже будут одинаковыми. Значит, в ответе a xor b на этих позициях получить 1 нельзя.

Но как только мы дошли до первого сверху бита, где l и r различаются, ситуация резко меняется.

Почему?

Потому что это означает, что внутри отрезка есть числа:

• с 0 в этом бите,
• и с 1 в этом бите.

Тогда можно подобрать пару чисел так, чтобы в этой позиции XOR дал 1. Более того, на всех более младших позициях тоже можно добиться единиц.

Следовательно, если старший различающийся бит имеет номер k, то максимальный ответ будет выглядеть так:

111...111

где единицы стоят на позициях от k до 0.

Иными словами, ответ равен:

2^(k + 1) - 1

Почему достаточно вычислить l xor r

Рассмотрим число:

x = l xor r

Что оно показывает?

• если в некотором бите l и r совпадают, то в x там будет 0;
• если различаются, то в x там будет 1.

Значит, старший установленный бит числа x — это как раз первый сверху бит, где l и r различаются.

После этого остаётся только построить число, состоящее из одних единиц на всех позициях от этого бита и ниже.

Разберём пример

Пусть:

l = 8, r = 16

В двоичном виде:

• 8 = 01000
• 16 = 10000

Тогда:

8 xor 16 = 11000

Старший установленный бит находится на позиции 4. Значит, ответ должен быть числом из пяти единиц:

11111₂ = 31

Это и есть максимальное возможное значение.

Почему ответ всегда имеет вид из одних единиц

Представим, что l и r впервые различаются в некотором старшем бите.

Тогда:

• выше этого бита у всех чисел из отрезка префикс одинаковый,
• в этом бите можно получить различие,
• ниже этого бита отрезок уже достаточно широк, чтобы подобрать числа с нужными младшими битами.

Поэтому максимальный XOR не будет каким-то сложным числом. Он всегда будет состоять из подряд идущих единиц от старшего различающегося бита до нулевого.

Это очень важная идея задачи.

Способ 1. Построить ответ циклом

Сначала найдём:

x = l ^ r

Потом будем строить ответ так:

• пока в x есть биты,
• сдвигаем ответ влево,
• добавляем справа единицу.

Например, если x занимает 5 бит, то мы получим:

• 1
• 11
• 111
• 1111
• 11111

Именно это нам и нужно.

Реализация на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long l, r;
    cin >> l >> r;

    long long x = l ^ r;
    long long ans = 0;

    while (x > 0) {
        ans = (ans << 1) | 1;
        x >>= 1;
    }

    cout << ans << '\n';
    return 0;
}

Реализация на Python

l, r = map(int, input().split())

x = l ^ r
ans = 0

while x > 0:
    ans = (ans << 1) | 1
    x >>= 1

print(ans)

Способ 2. Через длину двоичной записи

Если число x = l ^ r имеет длину k бит, то ответ — это число из k единиц.

Такое число равно:

(1 << k) - 1

В Python длину двоичной записи удобно получать через bit_length().

Короткая версия на Python

l, r = map(int, input().split())

x = l ^ r
print((1 << x.bit_length()) - 1)

Пошаговый алгоритм

1. Считать l и r.
2. Вычислить x = l xor r.
3. Найти старший бит, в котором l и r различаются.
4. Построить число, состоящее из единиц на всех позициях от этого бита и ниже.
5. Вывести ответ.

Почему алгоритм работает

Докажем это аккуратно.

Пусть старший бит, в котором l и r различаются, имеет номер k.

1. Выше бита k получить единицы нельзя

Так как это первый различающийся сверху бит, все более старшие биты у l и r совпадают. Значит, все числа из отрезка [l, r] имеют там одинаковый префикс. Следовательно, у любых a и b из этого отрезка в этих битах XOR равен 0.

2. В бите k можно получить единицу

Так как l и r различаются в бите k, внутри отрезка существуют числа по обе стороны этого разделения: с 0 и с 1 в этом бите. Значит, можно выбрать a и b так, чтобы XOR в этой позиции был равен 1.

3. Во всех младших битах тоже можно получить единицы

После первого различия отрезок уже охватывает достаточно большой диапазон значений, чтобы подобрать пару чисел с нужными комбинациями младших битов. Поэтому на всех битах ниже k можно добиться единицы.

Значит, максимальное значение XOR равно числу вида:

111...111

на позициях от k до 0.

Что и требовалось доказать.

На что обратить внимание

Случай l = r

Тогда:

• l ^ r = 0,
• различающихся битов нет,
• можно выбрать только одинаковые числа,
• ответ равен 0.

Наш код обрабатывает этот случай автоматически.

Почему не нужен перебор

Хотя формально нужно выбрать пару чисел, на самом деле задача полностью решается по двоичной записи границ отрезка. Это типичная идея в задачах на битовые операции: искать не сами числа, а свойства их битов.

Сложность

Пусть число имеет не более 60 бит, потому что r ≤ 10^18.

Тогда:

• время работы: O(log r);
• память: O(1).

Это очень быстро.

Итог

В этой задаче главное — заметить, что максимум a xor b определяется не конкретным выбором пары, а первым старшим битом, в котором l и r различаются.

После этого ответ становится очень простым: это число, состоящее из подряд идущих единиц.

Именно такие задачи хорошо показывают силу двоичного мышления: вместо перебора огромного количества вариантов мы находим одно короткое свойство, которое сразу даёт решение.