Замените все вхождения X на Y или добавьте элемент K в массив для запросов Q.

Для пустого массива запросов A[] и Q двух типов 1 и 2 , представленных запросами1 и запросами2 соответственно, задача состоит в том, чтобы найти конечное состояние массива. Запросы бывают следующего типа:

• Если type[i]=1 , вставьте query1[i] (скажем, K ) в конец массива A . Значение query2[i] = -1 для этого типа запроса.
• Если type[i]=2 , замените все вхождения запросов1[i] (скажем, X ) на запросы2[i] (скажем Y ) в A[].

Примеры:

Input: Q = 3, type = [1, 1, 2], queries1 = [1, 2, 1], queries2 = [-1, -1, 2]
Output: A = [2, 2]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. 
After 2nd query, A = [1, 2]. 
After 3rd query, A = [2, 2].

Input: Q = 5, type = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 3], queries2 = [-1, -1, -1, 2, 1]
Output: A = [2, 2, 1]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. After 2nd query, A = [1, 2]. 
After 3rd query, A = [1, 2, 3]. 
After 4th query A = [2, 2, 3]. 
After 5th query, A = [2, 2, 1].

Input: Q=5, type = [1, 1, 1, 2, 2], queries1 = [1, 2, 3, 1, 2], queries2 = [-1, -1, -1, 2, 3]
Output: A = [3, 3, 3]
Explanation: Initially A[] is empty. 
After 1st query, A = [1]. After 2nd query, A = [1, 2]. 
After 3rd query, A = [1, 2, 3]. After 4th query, A = [2, 2, 3]. 
After 5th query, A = [3, 3, 3].

Наивный подход:

The basic way to solve the problem is to iterate through all the queries type, and for each type[i] = 1 add queries1[i] in A else if type[i]=2, find all occurrences of queries1[i] in A and replace it with queries2[i].

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

Эффективный подход: проблема может быть эффективно решена с использованием хеширования на основе следующей идеи:

Use a map to store indices of the elements in the array. For  all queries of type 2, find the values to be replaced and give those indices to the replaced values.

Для реализации подхода выполните следующие шаги:

• Перебрать все типы запросов с типами [i] = 1 (для вставки в A ) и с типами [i] = 2 для замены запросов1[i] запросами2[i] в A.
• Для всех типов запросов[i] = 2 , если запросы1[i] присутствуют в хэш-карте, скопируйте связанный с ним вектор в запросы2[i] и сотрите все запросы1[i].
• После выполнения всех запросов скопируйте все значения хэш-карты обратно в исходный вектор A с использованием индексов, хранящихся в хэш-карте (ключи, хранящиеся в виде элементов, и связанные векторы, в которых хранятся индексы этого элемента).
• Теперь исходный вектор A обновляется и является конечным состоянием массива.

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

Временная сложность: O(Q * K), где K — максимальный размер сформированного вектора.
Вспомогательное пространство: O(K)