Сдать решение задачи D-Новогодние гирлянды Полный балл: 100 Ограничение времени: 1 c Ограничение реального времени: 5 с Ограничение памяти: 256M Новогодние гирлянды Перед Новым годом Дед Мороз поручил Максиму важное задание. У Деда Мороза есть гирлянда из n светодиодных лампочек. Режим мигания и цвет каждой лампочки кодируются целым числом: режим і-й лампочки задан числом аi. Максим считает, что пара лампочек выглядит гармонично, если их режимы похожи. Для пары лампочек с номерами і <ј он вычисляет где ⊕ обозначает побитовое исключающее ИЛИ. Чем меньше это значение, тем гармоничнее пара. Сначала Максим рассматривает все пары лампочек и определяет минимальное значение аi ⊕ аj – это значение он называет «гармоничностью гирлянды». Далее происходят q изменений. Каждое изменение задаётся двумя числами: позицией роs и новым значением Х. После каждого изменения значение на позиции роs заменяется на Х. После каждого изменения требуется определить новое минимальное значение аi ⊕ аj среди всех пар лампочек. Формат входных данных Первая строка содержит два целых числа n, q – количество лампочек в гирлянде и количество изменений (2 ≤ n, q≤ 105). Вторая строка содержит n целых чисел а1, a2,..., ап (0 ≤ аi ≤ 1018), где аi — режим і-й лампочки. Каждая из следующих q строк содержит по два целых числа роs, Х (1 ≤ pos ≤ n, 0 ≤ X ≤ 109) - номер лампочки, которую меняют, и новое значение режима Х, которое устанавливают на эту позицию. Формат выходных данных Выведите q + 1 строку. В первой строке ответ для изначального массива без изменений. Затем в каждой из следующих q строк должно быть одно целое число минимальное значение аi ⊕ аj по всем парам 1 ≤ i < j ≤ n после выполнения соответствующего запроса. Примеры Входные данные 5 2 3 1 2 5 4 3 100 4 1000 Результат работы

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

1. Считать входные данные:
   • Считать числа n и q.
   • Считать массив a из n чисел.
   • Считать q пар чисел (pos, X).
2. Вычислить начальное минимальное значение XOR:
   • Для каждой пары (i, j) где 1 ≤ i < j ≤ n, вычислить a[i] ⊕ a[j].
   • Найти минимальное значение среди всех полученных XOR значений.
   • Вывести это значение.
3. Выполнить q изменений:
   • Для каждого изменения (pos, X):
   • Заменить a[pos-1] на X.
   • Вычислить новое минимальное значение XOR как в шаге 2.
   • Вывести это значение.

Пример кода на Python:

def solve():
    n, q = map(int, input().split())
    a = list(map(int, input().split()))

    def calculate_min_xor(arr):
        min_xor = float('inf')
        for i in range(len(arr)):
            for j in range(i + 1, len(arr)):
                min_xor = min(min_xor, arr[i] ^ arr[j])
        return min_xor

    print(calculate_min_xor(a))

    for _ in range(q):
        pos, x = map(int, input().split())
        a[pos - 1] = x
        print(calculate_min_xor(a))

solve()

Для входных данных:

5 2
3 1 2 5 4
3 100
4 1000

Результат работы:

1. Начальный массив: [3, 1, 2, 5, 4]
   • (3 ⊕ 1) = 2
   • (3 ⊕ 2) = 1
   • (3 ⊕ 5) = 6
   • (3 ⊕ 4) = 7
   • (1 ⊕ 2) = 3
   • (1 ⊕ 5) = 4
   • (1 ⊕ 4) = 5
   • (2 ⊕ 5) = 7
   • (2 ⊕ 4) = 6
   • (5 ⊕ 4) = 1
   • Минимальное XOR значение: 1
2. Изменение 1: pos = 3, x = 100
   • Новый массив: [3, 1, 100, 5, 4]
   • (3 ⊕ 1) = 2
   • (3 ⊕ 100) = 97
   • (3 ⊕ 5) = 6
   • (3 ⊕ 4) = 7
   • (1 ⊕ 100) = 101
   • (1 ⊕ 5) = 4
   • (1 ⊕ 4) = 5
   • (100 ⊕ 5) = 105
   • (100 ⊕ 4) = 104
   • (5 ⊕ 4) = 1
   • Минимальное XOR значение: 1
3. Изменение 2: pos = 4, x = 1000
   • Новый массив: [3, 1, 100, 1000, 4]
   • (3 ⊕ 1) = 2
   • (3 ⊕ 100) = 97
   • (3 ⊕ 1000) = 1003
   • (3 ⊕ 4) = 7
   • (1 ⊕ 100) = 101
   • (1 ⊕ 1000) = 1001
   • (1 ⊕ 4) = 5
   • (100 ⊕ 1000) = 900
   • (100 ⊕ 4) = 104
   • (1000 ⊕ 4) = 1004
   • Минимальное XOR значение: 2

Ответ:

1
1
2