Найдите элемент массива после запросов Q на основе заданных условий

Дан массив arr[] длины N и Q запросов 3-х типов (1, 2, 3), операции которых следующие:

• Тип 1: запрос имеет ввод как 1 , и задача состоит в том, чтобы перевернуть массив.
• Тип 2: запрос имеет ввод как (2 x) и задачу найти индекс x в массиве результатов.
• Тип 3: запрос имеет ввод как (3 xy) , и задача состоит в том, чтобы поменять местами элементы с индексами x и y в массиве.

Задача состоит в том, чтобы напечатать результат для запроса типа 2 .

Примеры:

Input: N = 5, arr[] = {3, 7, 8, 1, 33}, Q = 4, Queries[][] = {{1}, {2, 8}, {3, 2, 4}, {2, 1}
Output: 2 1
Explanation: Process query wise first is 1 so reverse the list [33, 1, 8, 7, 3], Second query 2 8 so find index of element 8 which is 2, third query is 3 2 4 so swap 2nd and 4th index new array=[33, 1, 3, 7, 8] now the last query is 2 1 so find index of element 1 which is 1 so output 2 1.

Input: N = 6, arr[] = {6, 33, 9, 22, 45, 4}, Q = 5, Queries[][] = {{1}, {3, 0, 4}, {2, 33}, {1}, {2, 9}}
Output: 0 2

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

• Используйте переменную flag =1 и для каждого запроса типа 1 умножайте flag * -1 , чтобы для отрицательного значения он указывал на обращение списка и манипулировал вычислениями в обратном порядке, а не напрямую обращал массив, и таким образом уменьшал временную сложность.
• Теперь для запроса типа 3 xy используйте структуру данных карты для хранения индекса и элемента в виде пар ключ-значение и прямого обмена значениями в O(1) .
• Наконец, для запроса типа 2 x напрямую извлеките индекс.

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

• Инициализируйте карту mp = {}, чтобы сохранить элемент и его индекс в массиве в виде пары ключ-значение .
• Инициализируйте флаг переменной как 1 , чтобы отслеживать количество раз, когда массив переворачивается.
• Перебрать диапазон [0, Q), используя переменную i , и выполнить следующие задачи:
  • Во-первых, проверьте тип запроса, принимая каждый запрос в качестве входных данных.
  • Для запроса типа 1 вместо реверсирования вручную, что увеличит временную сложность, измените знак флага переменной, чтобы обозначить, что массив является нормальным или реверсивным.
  • Для запроса типа 2 найдите индекс заданного значения на карте и, если массив не перевернут, выведите в качестве результата значение m[x] . В противном случае выведите значение (N – m[x] – 1) .
  • Для запроса типа 3 сначала найдите значения по заданному индексу, а затем поменяйте местами значение и индекс в списке и на карте соответственно.

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

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