Побитовое ИЛИ побитового И всех подмножеств массива для Q запросов

Опубликовано: 22 Сентября, 2022

Имея два массива arr[] размера N и query[] размера Q, задача состоит в том, чтобы найти ИЛИ для И подмножеств массива. В каждом запросе вам дается индекс и значение, вы должны заменить значение в данном индексе массивов заданным значением и распечатать ИЛИ всех подмножеств массива после каждого запроса.

Примеры:

Input: arr[] = {3, 5, 7}, N = 3, queries[] = {{1, 2}, {2, 1}}, Q = 2 
Output: 7 
                3
Explanation: 
For the first query replace the value at index 1 with value 2, updated array arr[] is {3, 2, 7}.
Then take AND of all subsets i.e. AND(3) = 3, AND(2) = 2, AND(7) = 7, AND(3, 2) = 2, AND(3, 7) = 3, AND(3, 2, 7) = 2.
OR of the AND of all subsets are OR(3, 2, 7, 2, 3, 2) = 7.
Now, for the second query replace the value at index 2 with value 1, updated array arr[] is {3, 2, 1}.
Then take AND of all subsets i.e. AND(3) = 3, AND(2) = 2, AND(1) = 1, AND(3, 2) = 2, AND(3, 1) = 1, AND(3, 2, 1) = 0. 
OR of the AND of all subsets OR(3, 2, 1, 2, 1, 0) = 3.

Input: arr[] = {1, 2, 3}, N = 3, queries[] = {{2, 4}, {1, 8}}, Q = 2 
Output: 7  
               13

Подход: Эту задачу можно решить с помощью жадного алгоритма. Выполните следующие шаги, чтобы решить проблему:

  • Инициализируйте массив bits[] размером 32 и сохраните количество установленных битов всех элементов.
  • Выполните итерацию в диапазоне [0, Q-1], используя переменную p :
    • Сначала вычтите биты предыдущего значения, а затем добавьте биты нового значения.
    • Итерация в диапазоне [0, 31] с использованием переменной i :
      • Если текущий бит установлен для предыдущего значения, то вычтите один бит из массива bits[] по i -му индексу.
      • Если текущий бит установлен для нового значения, то добавьте один бит в массив битов[] по индексу ith .
    • Замените новое значение из предыдущего значения в данном массиве arr[].
    • Инициализируйте переменную и сохраните ИЛИ массива битов .
    • Итерация в диапазоне [0, 31] с использованием переменной i :
      • Если текущий бит не равен 0, то добавить ИЛИ текущего бита в ans .
    • После выполнения вышеуказанных шагов выведите ответы в качестве необходимого ответа для каждого запроса.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(max(N, Q))
Вспомогательное пространство: O(1)

РЕКОМЕНДУЕМЫЕ СТАТЬИ