Выполнять заданные запросы в очереди в соответствии с заданными правилами

Дана очередь, состоящая из первых N натуральных чисел и запросов Query[][] типа {E, X}, задача состоит в том, чтобы выполнить заданные запросы в заданной очереди по следующим правилам:

• Если значение E равно 1 , то передний элемент извлекается из очереди.
• Если значение E равно 2 , то удалите значение X из очереди, если оно существует.
• Если значение E равно 3 , то найти позицию X в очереди, если она существует. В противном случае выведите «-1» .

Примеры:

Input: N = 5, Query[][] = {{1, 0}, {3, 3}, {2, 2}}
Output: 2
Explanation:
Initially queue looks like { 1, 2, 3, 4, 5 }. Following are the operations performed according to the queries given: 
1st query  E = 1, X = 0 -> 1 is popped out changing queue to { 2, 3, 4, 5 }.
2nd query E = 3, X = 3 -> The position of 3 is printed. 
3rd query E = 2, X = 2 -> 2 is removed from queue changing queue to { 3, 4, 5 }.

Input: N = 5, Query[][] = {{1, 0}, {3, 1}}
Output: -1

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

• Инициализируйте переменную, скажем, countE1 как 0 , чтобы подсчитать количество вхождений события E1 .
• Увеличьте значение countE1 на 1 , если запрос имеет тип E1 .
• Поддерживайте заданную структуру данных, в которой хранятся элементы, удаляемые при выполнении операций запросов.
• Для запроса типа 3 выполните следующие действия:
  • Инициализируйте переменную, скажем, position для хранения начальной позиции X .
  • Найдите значение X в наборе, чтобы проверить, удален ли X уже или нет, и если X присутствует в наборе, выведите -1 . В противном случае найдите положение X .
  • Пройдите через набор с помощью итератора, скажите это , и если его значение > X , то выйдите из цикла. В противном случае уменьшите позицию на 1 .
  • Распечатайте конечную позицию хранилища X в переменной position.

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

Сложность времени:

• Для запроса типа 1: O(1)
• Для запроса типа 2: O(log N)
• Для запроса типа 3: O(N ² log N)

Вспомогательное пространство: O(N)