Encuentre la suma de la array después de realizar cada consulta

Dada una array arr[] de consultas de tamaño N y Q donde cada consulta contiene dos números enteros X e Y , la tarea es encontrar la suma de una array después de realizar cada consulta Q de modo que para cada consulta, el elemento de la array arr[ ] con el valor X se actualiza a Y . Encuentre la suma de la array después de cada consulta.

Ejemplos:

Entrada: arr[] ={1, 2, 3, 4}, Q = {(1, 2), (3, 4), (2, 4)}
Salida: 11 12 16
Explicación:
la primera operación es reemplazar cada 1 con 2
Entonces la array se convierte en ar[ ] ={2, 2, 3, 4} y suma = 11 La
segunda operación es reemplazar cada 3 con 4
Entonces la array se convierte en ar[ ] ={2, 2, 4, 4} y suma = 12 La
tercera operación es reemplazar cada 2 con 4
Entonces la array se convierte en ar[ ] ={4, 4, 4, 4} ans sum = 16

Entrada: arr[] = {1}, Q = {(1, 2)}
Salida: 2

Enfoque ingenuo: El enfoque ingenuo consiste en recorrer cada consulta y, para cada consulta, actualizar cada elemento de la array arr[] con el valor X a Y recorriendo la array. Imprime la suma de todos los elementos en arr[] después de realizar cada consulta.
Complejidad temporal: O(N*Q) 
Espacio auxiliar: O(1)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es calcular la suma de todos los elementos en la array (por ejemplo, sum ) arr[] y almacenar la frecuencia de todos los elementos en un mapa_desordenado ( por ejemplo, M ). Para cada consulta (X, Y) haga lo siguiente:

1. Encuentre la frecuencia de X de unordered_map M .
2. Disminuye sum por X*M[X] , para excluir la suma de X .
3. Incremente la suma en Y*M[X] , para excluir la suma de Y .
4. Aumente la frecuencia de Y en el mapa en M[X] .
5. Finalmente, imprima la suma y elimine X del mapa M .

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that solves the given queries
void solve(int ar[], int n, int b[],
           int c[], int q)
{
    // This map will store the
    // frequency of each element
    unordered_map<int, int> mp;
 
    // sum stores the sum of
    // all elements of array
    int sum = 0;
 
    for (int x = 0; x < n; x++) {
        sum += ar[x];
        mp[ar[x]]++;
    }
 
    // Process the queries
    for (int x = 0; x < q; x++) {
 
        // Find occurrence of
        // b[x] from map
        int occur1 = mp[b[x]];
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.erase(b[x]);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        mp] += occur1;
 
        // Print sum
        cout << sum << " ";
    }
}
 
// Driver Code
int main()
{
    // Given arr[]
    int ar[] = { 1, 2, 3, 4 };
    int n = 4;
 
    // Given Queries
    int q = 3;
    int b[] = { 1, 3, 2 };
    int c[] = { 2, 4, 4 };
 
    // Function Call
    solve(ar, n, b, c, q);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
// Function that solves the given queries
static void solve(int ar[], int n, int b[],
                   int c[], int q)
{
     
    // This map will store the
    // frequency of each element
    Map<Integer, Integer> mp = new HashMap<>();
 
    // sum stores the sum of
    // all elements of array
    int sum = 0;
 
    for(int x = 0; x < n; x++)
    {
        sum += ar[x];
        mp.put(ar[x], mp.getOrDefault(ar[x], 0) + 1);
    }
     
    // Process the queries
    for(int x = 0; x < q; x++)
    {
         
        // Find occurrence of
        // b[x] from map
        int occur1 = mp.get(b[x]);
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.remove(b[x]);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        mp.put(c[x], mp.get(c[x]) + occur1);
         
        // Print sum
        System.out.print(sum + " ");
    }
}
 
// Driver Code
public static void main (String[] args)
{
     
    // Given arr[]
    int ar[] = { 1, 2, 3, 4 };
    int n = 4;
     
    // Given queries
    int q = 3;
    int b[] = { 1, 3, 2 };
    int c[] = { 2, 4, 4 };
     
    // Function call
    solve(ar, n, b, c, q);
}
}
 
// This code is contributed by offbeat

# Python3 program for the above approach
 
# Function that solves the given queries
def solve(ar, n, b, c, q):
   
    # This map will store the
    # frequency of each element
    mp = {}
     
    # sum stores the sum of
    # all elements of array
    sum = 0
 
    for x in range(n):
        sum += ar[x]
        mp[ar[x]] = mp.get(ar[x], 0) + 1
 
    # Process the queries
    for x in range(q):
       
        # Find occurrence of
        # b[x] from map
        occur1 = mp[b[x]]
 
        # Decrease sum
        sum = sum - occur1 * b[x]
 
        # Erase b[x] from map
        del mp[b[x]]
 
        # Increase sum
        sum = sum + occur1 * c[x]
 
        # Increase frequency
        # of c[x] in map
        mp] += occur1
 
        # Print sum
        print(sum, end = " ")
         
# Driver Code
if __name__ == '__main__':
   
    # Given arr[]
    ar = [ 1, 2, 3, 4 ]
    n = 4
 
    # Given Queries
    q = 3
    b = [ 1, 3, 2 ]
    c = [ 2, 4, 4 ]
 
    # Function Call
    solve(ar, n, b, c, q)
 
# This code is contributed by mohit kumar 29

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
     
// Function that solves
// the given queries
static void solve(int []ar, int n,
                  int []b, int []c,
                  int q)
{   
  // This map will store the
  // frequency of each element
  Dictionary<int,
             int> mp = new Dictionary<int,
                                      int>();
 
  // sum stores the sum of
  // all elements of array
  int sum = 0;
 
  for(int x = 0; x < n; x++)
  {
    sum += ar[x];
    if(mp.ContainsKey(ar[x]))
      mp[ar[x]] = mp[ar[x]] + 1;
    else
      mp.Add(ar[x], 1);
  }
 
  // Process the queries
  for(int x = 0; x < q; x++)
  {
    // Find occurrence of
    // b[x] from map
    int occur1 = mp[b[x]];
 
    // Decrease sum
    sum = sum - occur1 * b[x];
 
    // Erase b[x] from map
    mp.Remove(b[x]);
 
    // Increase sum
    sum = sum + occur1 * c[x];
 
    // Increase frequency
    // of c[x] in map
    if(mp.ContainsKey(c[x]))
      mp] = mp] + occur1;
 
    // Print sum
    Console.Write(sum + " ");
  }
}
 
// Driver Code
public static void Main(String[] args)
{   
  // Given []arr
  int []ar = {1, 2, 3, 4};
  int n = 4;
 
  // Given queries
  int q = 3;
  int []b = {1, 3, 2};
  int []c = {2, 4, 4};
 
  // Function call
  solve(ar, n, b, c, q);
}
}
 
// This code is contributed by Princi Singh

<script>
 
// Javascript program for the above approach
 
// Function that solves the given queries
function solve(ar, n, b, c, q)
{
    // This map will store the
    // frequency of each element
    var mp = new Map();
 
    // sum stores the sum of
    // all elements of array
    var sum = 0;
 
    for (var x = 0; x < n; x++) {
        sum += ar[x];
        if(mp.has(ar[x]))
            mp.set(ar[x], mp.get(ar[x])+1)
        else
            mp.set(ar[x], 1);
    }
 
    // Process the queries
    for (var x = 0; x < q; x++) {
 
        // Find occurrence of
        // b[x] from map
        var occur1 = mp.get(b[x]);
 
        // Decrease sum
        sum = sum - occur1 * b[x];
 
        // Erase b[x] from map
        mp.set(b[x], 0);
 
        // Increase sum
        sum = sum + occur1 * c[x];
 
        // Increase frequency
        // of c[x] in map
        if(mp.has(c[x]))
            mp.set(c[x], mp.get(c[x])+occur1)
        else
            mp.set(c[x], occur1);
 
        // Print sum
        document.write( sum + " ");
    }
}
 
// Driver Code
// Given arr[]
var ar = [1, 2, 3, 4];
var n = 4;
// Given Queries
var q = 3;
var b = [1, 3, 2];
var c = [2, 4, 4];
// Function Call
solve(ar, n, b, c, q);
 
</script>

11 12 16

Complejidad temporal: O(N + Q)  
Espacio auxiliar: O(N)