Reemplace todas las apariciones de X por Y o agregue el elemento K en Array para consultas Q

Dada una array vacía A[] & Q consultas de dos tipos 1 y 2 representadas por queries1 y queries2 respectivamente, la tarea es encontrar el estado final de la array. Las consultas son del siguiente tipo:

• Si type[i]=1 , inserte queries1[i] (digamos K ) al final de la array A . El valor de queries2[i] = -1 para este tipo de consulta.
• Si type[i]=2 , reemplace todas las ocurrencias de queries1[i] (digamos X ) con queries2[i] (digamos Y ) en A[].

Ejemplos:

Entrada: Q = 3, tipo = [1, 1, 2], consultas1 = [1, 2, 1], consultas2 = [-1, -1, 2]
Salida: A = [2, 2]
Explicación: Inicialmente A [] esta vacio. 
Después de la primera consulta, A = [1]. 
Después de la segunda consulta, A = [1, 2]. 
Después de la tercera consulta, A = [2, 2].

Entrada: Q = 5, tipo = [1, 1, 1, 2, 2], consultas1 = [1, 2, 3, 1, 3], consultas2 = [-1, -1, -1, 2, 1]
Salida: A = [2, 2, 1]
Explicación: Inicialmente A[] está vacío. 
Después de la primera consulta, A = [1]. Después de la segunda consulta, A = [1, 2]. 
Después de la tercera consulta, A = [1, 2, 3]. 
Después de la cuarta consulta A = [2, 2, 3]. 
Después de la quinta consulta, A = [2, 2, 1].

Entrada: Q=5, tipo = [1, 1, 1, 2, 2], consultas1 = [1, 2, 3, 1, 2], consultas2 = [-1, -1, -1, 2, 3]
Salida: A = [3, 3, 3]
Explicación: Inicialmente A[] está vacío. 
Después de la primera consulta, A = [1]. Después de la segunda consulta, A = [1, 2]. 
Después de la tercera consulta, A = [1, 2, 3]. Después de la cuarta consulta, A = [2, 2, 3]. 
Después de la quinta consulta, A = [3, 3, 3].

Enfoque ingenuo:

La forma básica de resolver el problema es iterar a través de todo el tipo de consultas , y para cada tipo[i] = 1 , agregue consultas1[i] en A ; de lo contrario, si tipo[i]=2 , encuentre todas las ocurrencias de consultas1[i] en A y reemplácelo con queries2[i] .

Tiempo Complejidad: O(Q ² )
Espacio Auxiliar:O(1)

Enfoque eficiente: el problema se puede resolver de manera eficiente utilizando Hashing basado en la siguiente idea:

Use un mapa para almacenar índices de los elementos en la array. Para todas las consultas de tipo 2, encuentre los valores que se reemplazarán y dé esos índices a los valores reemplazados.

Siga los pasos a continuación para implementar el enfoque:

• Iterar a través de cada tipo de consulta de tipos [i] = 1 (para inserción en A ) y tipos[i] = 2 para reemplazar consultas1[i] con consultas2[i] en A.
• Para todos los tipos de consultas[i] = 2 , si consultas1[i] está presente en el hashmap, copie el vector asociado a él en consultas2[i] y borre todas las consultas1[i]. 
• Después de realizar todas las consultas, copie todos los valores del hashmap nuevamente en el vector original A , con el uso de índices almacenados en el hashmap (claves almacenadas como elementos y vectores asociados que almacenan índices de ese elemento).
• Ahora el vector A original se actualiza y es el estado final de la array

A continuación se muestra la implementación del enfoque anterior:

// C++ code to implement the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the final state of array
vector<int> processQ(int Q, vector<int> types,
                     vector<int> queries1,
                     vector<int> queries2)
{
    // Initializing an unordered map
    unordered_map<int, vector<int> > indices;
    int cnt = 0;
    for (int i = 0; i < Q; i++) {
        if (types[i] == 1) {
            indices[queries1[i]].push_back(cnt++);
        }
        else {
            for (auto& x : indices[queries1[i]])
                indices[queries2[i]].push_back(x);
            indices[queries1[i]].clear();
        }
    }
 
    vector<int> A(cnt);
    for (auto& x : indices) {
        for (auto& y : x.second)
            A[y] = x.first;
    }
 
    return A;
}
 
// Driver code
int main()
{
    vector<int> types = { 1, 1, 2 };
    vector<int> queries1 = { 1, 2, 1 };
    vector<int> queries2 = { -1, -1, 2 };
 
    // Function call
    vector<int> ans
        = processQ(types.size(), types,
                   queries1, queries2);
    for (auto& x : ans)
        cout << x << " ";
    return 0;
}

import java.util.*;
import java.io.*;
 
// Java program for the above approach
 
class GFG{
 
    // Function to find the final state of array
    static ArrayList<Integer> processQ(int Q,
                                       ArrayList<Integer> types,
                                       ArrayList<Integer> queries1,
                                       ArrayList<Integer> queries2)
    {
        // Initializing an unordered map
        HashMap<Integer, ArrayList<Integer>> indices =
          new HashMap<Integer, ArrayList<Integer>>();
 
        int cnt = 0;
        for (int i = 0 ; i < Q ; i++) {
            if (types.get(i) == 1) {
                if(!indices.containsKey(queries1.get(i))){
                    indices.put(queries1.get(i), new ArrayList<Integer>());
                }
                indices.get(queries1.get(i)).add(cnt++);
            }
            else {
                if(indices.containsKey(queries1.get(i))){
                    for (int x : indices.get(queries1.get(i))){
                        if(!indices.containsKey(queries2.get(i))){
                            indices.put(queries2.get(i), new ArrayList<Integer>());
                        }
                        indices.get(queries2.get(i)).add(x);
                    }
                    indices.get(queries1.get(i)).clear();
                }
            }
        }
 
        ArrayList<Integer> A = new ArrayList<Integer>();
        for(int i = 0 ; i < cnt ; i++){
            A.add(0);
        }
 
        for (Map.Entry<Integer, ArrayList<Integer>> x : indices.entrySet()){
            for (int y : x.getValue()){
                A.set(y, x.getKey());
            }
        }
 
        return A;
    }
 
    // Driver Code
    public static void main(String args[])
    {
        ArrayList<Integer> types = new ArrayList<Integer>(
            List.of( 1, 1, 2 )
        );
        ArrayList<Integer> queries1 = new ArrayList<Integer>(
            List.of( 1, 2, 1 )
        );
        ArrayList<Integer> queries2 = new ArrayList<Integer>(
            List.of( -1, -1, 2 )
        );
 
        // Function call
        ArrayList<Integer> ans = processQ(types.size(), types, queries1, queries2);
        for (int x : ans){
            System.out.print(x + " ");
        }
        System.out.println("");
       }
}
 
// This code is contributed by entertain2022.

# python3 code to implement the above approach
 
# Function to find the final state of array
def processQ(Q, types, queries1, queries2):
 
        # Initializing an unordered map
    indices = {}
    cnt = 0
    for i in range(0, Q):
        if (types[i] == 1):
            if queries1[i] in indices:
                indices[queries1[i]].append(cnt)
            else:
                indices[queries1[i]] = [cnt]
            cnt += 1
 
        else:
            if queries1[i] in indices:
                for x in indices[queries1[i]]:
                    if queries2[i] in indices:
                        indices[queries2[i]].append(x)
                    else:
                        indices[queries2[i]] = [x]
 
                indices[queries1[i]] = []
 
    A = [0 for _ in range(cnt)]
 
    for x in indices:
        for y in indices[x]:
            A[y] = x
 
    return A
 
# Driver code
if __name__ == "__main__":
 
    types = [1, 1, 2]
    queries1 = [1, 2, 1]
    queries2 = [-1, -1, 2]
 
    # Function call
    ans = processQ(len(types), types,
                   queries1, queries2)
    for x in ans:
        print(x, end=" ")
 
    # This code is contributed by rakeshsahni

// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG
{
 
  // Function to find the final state of array
  static List<int> processQ(int Q, List<int> types, List<int> queries1, List<int> queries2)
  {
    // Initializing an unordered map
    Dictionary<int, List<int>> indices = new Dictionary<int, List<int>>();
    int cnt = 0;
    for (int i = 0 ; i < Q ; i++) {
      if (types[i] == 1) {
        if(!indices.ContainsKey(queries1[i])){
          indices.Add(queries1[i], new List<int>());
        }
        indices[queries1[i]].Add(cnt++);
      }
      else {
        if(indices.ContainsKey(queries1[i])){
          foreach (int x in indices[queries1[i]]){
            if(!indices.ContainsKey(queries2[i])){
              indices.Add(queries2[i], new List<int>());
            }
            indices[queries2[i]].Add(x);
          }
          indices[queries1[i]].Clear();
        }
      }
    }
 
    List<int> A = new List<int>();
    for(int i = 0 ; i < cnt ; i++){
      A.Add(0);
    }
 
    foreach (KeyValuePair<int, List<int>> x in indices) {
      foreach (int y in x.Value){
        A[y] = x.Key;
      }
    }
 
    return A;
  }
 
  // Driver code
  public static void Main(string[] args){
 
    List<int> types = new List<int>{ 1, 1, 2 };
    List<int> queries1 = new List<int>{ 1, 2, 1 };
    List<int> queries2 = new List<int>{ -1, -1, 2 };
 
    // Function call
    List<int> ans = processQ(types.Count, types, queries1, queries2);
    foreach (int x in ans){
      Console.Write(x + " ");
 
    }
  }
}
 
// This code is contributed by subhamgoyal2014.

<script>
// JavaScript code to implement the above approach
 
// Function to find the final state of array
function processQ(Q, types, queries1, queries2)
{
 
    // Initializing an unordered object
    var indices = {};
    var cnt = 0;
    for (var i = 0; i < Q; i++)
    {
        if (types[i] == 1)
        {
            if (indices.hasOwnProperty(queries1[i]))
                indices[queries1[i]].push(cnt);
            else
                indices[queries1[i]] = [cnt];
            cnt += 1;
        }
 
        else
        {
            if (indices.hasOwnProperty(queries1[i]))
            {
                for (var j = 0; j < indices[queries1[i]].length; j++)
                {
                    var x = indices[queries1[i]][j];
                    if (indices.hasOwnProperty(queries2[i]))
                        indices[queries2[i]].push(x);
                    else
                        indices[queries2[i]] = [x];
                }
 
                indices[queries1[i]] = [];
            }
        }
    }
     
    var A = new Array(cnt).fill(0);
 
     
    for (const [keys, values] of Object.entries(indices))
    {
        for (var i = 0; i < values.length; i++)
        {
            var y = values[i];
            A[y] = keys;
        }
    }
         
    return A;
}
 
// Driver code
var types = [1, 1, 2];
var queries1 = [1, 2, 1];
var queries2 = [-1, -1, 2];
 
// Function call
var ans = processQ(types.length, types,
                   queries1, queries2);
for (var i = 0; i < ans.length; i++)
{
   document.write(ans[i] + " ");
}
 
// This code is contributed by phasing17
</script>

2 2 

Complejidad Temporal: O(Q * K) donde K es el tamaño máximo del vector formado
Espacio Auxiliar: O(K)