Найдите первое неудаленное целое число от K до N в заданном несвязанном графе после выполнения Q запросов

Для данного положительного целого числа N , представляющего множество целых чисел [1, N] и массива запросов[] длины Q типа {L, K} , задача состоит в том, чтобы выполнить заданные запросы в соответствии со следующими правилами и вывести результат:

• Если значение L равно 1 , то удалите заданное целое число K .
• Если значение L равно 2 , то выведите первое целое число от K до N , которое не удаляется.

Примечание. Когда все элементы справа будут удалены, ответ будет -1 .

Примеры:

Input: N = 3, queries[] = {{2, 1}, {1, 1}, {2, 1}, {2, 3}}
Output: 1 2 3
Explanation:
For the first query: the rightmost element for 1 is 1 only.
After the second query: 1 is deleted.
For the third query: the rightmost element for 1 is 2.
For the fourth query: the rightmost element for 3 is 3.

Input: N = 5, queries = {{2, 1}, {1, 3}, {2, 3}, {1, 2}, {2, 2}, {1, 5}, {2, 5}}
Output: 1 4 4 -1 

Подход: Данная проблема может быть решена с использованием структуры данных Disjoint Set Union. Изначально все элементы находятся в разных наборах, для запроса первого типа выполните операцию объединения над заданным целым числом. Для второго типа запроса получите родителя данной вершины и напечатайте значение, хранящееся в массиве graph[] . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте векторный график (N + 2) .
• Переберите диапазон [1, N+1], используя переменную i , и установите значение graph[i] как i .
• Переберите запросы [] с помощью переменной query и выполните следующие шаги:
  • Если query.first равен 1 , вызовите функциональную операцию Union(graph, query.second, query.second + 1) .
  • В противном случае вызовите функциональную операцию Get(graph, query.second) и присвойте ее переменной a . Теперь, если значение a равно (N + 1) , выведите -1 . В противном случае выведите в качестве результата значение графа [a] .

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

Временная сложность: O(M*log N)
Вспомогательное пространство: O(N)