Problem:


Score : 400 points

Problem Statement

You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.

You will now successively do the following Q operations:

In the i-th operation, you replace every element whose value is B_{i} with C_{i}.

For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

Constraints

All values in input are integers.

 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5} 

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

Output

Print Q integers S_{i} to Standard Output in the following format:

S_{1}
S_{2}
\vdots
S_{Q}

Note that S_{i} may not fit into a 32-bit integer.

Sample Input 1

4
1 2 3 4
3
1 2
3 4
2 4

Sample Output 1

11
12
16

Initially, the sequence A is 1,2,3,4.

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

4
1 1 1 1
3
1 2
2 1
3 5

Sample Output 2

8
4
4

Note that the sequence A may not contain an element whose value is B_{i}.

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



Sample input:
4
1 2 3 4
3
1 2
3 4
2 4


Sample output:
11
12
16

Submission status: Accepted

Solution code:
import collections
n=int(input())
a = list(map(int, input().split()))
q=int(input())
sum=sum(a)
c=collections.Counter(a)
for i in range(q):
    b=list(map(int, input().split()))
    sum=sum+(b[1]-b[0])*c[b[0]]
    print(sum)
    c[b[1]]+=c[b[0]]
    c[b[0]]=0

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = list(map(int,input().split()))
    total = sum(a)
    counter = Counter(a)
    q = int(input())
    for i in range(q):
        b,c = map(int,input().split())
        num_of_changed_num = counter[b]
        counter[b] = 0
        counter[c] += num_of_changed_num
        total -= b * num_of_changed_num
        total += c * num_of_changed_num
        print(total)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    n = int(input())
    d = defaultdict(int)
    res = 0
    for a in input().split():
        aa = int(a)
        d[int(aa)] += 1
        res += aa

    nq = int(input())
    for q in range(nq): 
        b, c = [int(i) for i in input().split()]
        res += (c - b) * d[b]
        d[c] += d[b]
        d[b] = 0
        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# N,M = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
# a = tuple(int(sys.stdin.readline()) for _ in range(N)) # multi line with single param
# a = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(N)) # multi line with multi param
# s = sys.stdin.readline().rstrip()
# N = int(sys.stdin.readline())
# INF = float("inf")
import sys,collections

N = int(sys.stdin.readline())
A = tuple(map(int,sys.stdin.readline().split())) # single line with multi param
Q = int(sys.stdin.readline())
BC = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(Q)) # multi line with multi param
co = collections.Counter(A)
s = sum(A)

for b,c in BC:
    if b in co:
        n = co[b]
        del(co[b])
        co[c] += n
        s += (c-b)*n
    print(s)

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().strip().split()))
k=int(input())
d=dict()
for i in range(10**5+1):
    d[i]=0
for i in range(n):
    d[arr[i]]=d[arr[i]]+1
sumi=0
for i in range(n):
    sumi=sumi+arr[i]
for i in range(k):
    a,b=[int(a) for a in input().split()]
    e1=d[a]
    d[b]=d[b]+e1
    sumi=sumi+(e1)*(b-a)
    print(sumi)
    d[a]=0

Submission status: Accepted

Solution code:
N = int(input())
ls = [0 for i in range(10**5)]
now = 0
A = list(map(int,input().split()))
for i in range(N):
    now += A[i]
    ls[A[i]-1] += 1
q = int(input())
for i in range(q):
    a,b = map(int,input().split())
    now += (b-a)*ls[a-1]
    print(now)
    ls[b-1] += ls[a-1]
    ls[a-1] = 0

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for _ in range(q):
    B, C = map(int, input().split())
    b.append(B)
    c.append(C)

imax = 10**5

d = [0]*imax
for i in range(n):
    d[a[i]-1] += 1

ans = sum(a)
for i in range(q):
    b_count = d[b[i]-1]
    d[c[i]-1] += b_count
    ans += (c[i]-b[i]) * b_count
    print(ans)
    d[b[i]-1] = 0

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]

A=[0]*(10**5+1)
for i in range(n):
  A[a[i]] += 1

sum_tmp = sum(a)
for i in range(q):
  b = bc[i][0]
  c = bc[i][1]
  A[c] += A[b]
  sum_tmp += (c-b) * A[b]
  A[b] = 0
  
  print(sum_tmp)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	a_list = LI()
	q = I()
	a_sum = sum(a_list)
	a_list_counter = Counter(a_list)
	for _ in range(q):
		b, c = LI()
		a_sum += (c-b)*a_list_counter[b]
		a_list_counter[c] += a_list_counter[b]
		a_list_counter[b] = 0
		print(a_sum)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array([int(a) for a in input().split()])
q = int(input())
bc = np.array([[int(a) for a in input().split()] for j in range(q)])

u, c = np.unique(a, return_counts=True)
dica = dict(zip(u, c))
#print(dica)

keys = dica.keys()

tmp = sum([ k*dica[k] for k in dica.keys()])


for i in range(q):
  t1, t2 = bc[i]
  if not t1 in keys:
    dica[t1] = 0
  if not t2 in keys:
    dica[t2] = 0

  tmp += dica[t1] * (t2 - t1)
  print(tmp)
  
  dica[t2] = dica[t1] + dica[t2]
  dica[t1] = 0

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
q = INT()
b = [0]*q
c = [0]*q
for i in range(q):
    bb, cc = MAP()
    b[i] = bb
    c[i] = cc

res = sum(a)
counter = Counter(a)
for i in range(q):
    res += counter[b[i]]*(c[i]-b[i])
    counter[c[i]] = counter[b[i]] + counter[c[i]]
    counter[b[i]] = 0
    print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	q = int(sys.stdin.readline())
	b = []
	c = []
	for i in range(q):
		bi, ci = map(int, sys.stdin.readline().split())
		b.append(bi)
		c.append(ci)
	v = {}
	for i in range(n):
		v[a[i]] = v.get(a[i], 0) + 1
	suma = sum(a)
	for i in range(q):
		suma += v.get(b[i], 0) * (c[i] - b[i])
		v[c[i]] = v.get(c[i], 0) +  v.get(b[i], 0)
		v[b[i]] = 0
		log.print(v)
		print(suma)
	


main()

Submission status: Accepted

Solution code:
N = 4
ARR = [1, 1, 1, 1]
Q = 3
SRR = [
    [1, 2],
    [2, 1],
    [3, 5]
]

N = 4
ARR = [1, 2, 3, 4]
Q = 3
SRR = [
    [1, 2],
    [3, 4],
    [2, 4],
]


#
# N = 2
# ARR = [1, 2]
# Q = 3
# SRR = [
#     [1, 100],
#     [2, 100],
#     [100, 1000]
# ]

N = int(input())
ARR = list(map(int,input().split()))
Q = int(input())
SRR = []

for i in range(Q):
    SRR.append(list(map(int,input().split())))


def calculate(n, arr, q, srr):
    dict = {}
    sumValue = sum(arr)
    for i in range(n):
        value = arr[i]
        if dict.get(value) == None:
            dict.__setitem__(value, 1)
        else:
            dict.__setitem__(value, dict.get(value) + 1)

    for i in range(q):
        fromValue = srr[i][0]
        toValue = srr[i][1]

        if dict.get(fromValue) == None:
            print(sumValue)
        else:
            fromNum = dict.get(fromValue)
            dict.__setitem__(fromValue, 0)
            sumValue += fromNum * (toValue - fromValue)
            if dict.get(toValue) == None:
                dict.__setitem__(toValue, fromNum)
            else:
                dict.__setitem__(toValue, dict.get(toValue) + fromNum)
            print(sumValue)


calculate(N, ARR, Q, SRR)

Submission status: Accepted

Solution code:
import collections
n=int(input())
List=list(map(int,input().split()))
hashmap=collections.defaultdict(int)
q=int(input())
total=0
for x in List:
    total+=x
    hashmap[x]+=1
for _ in range(q):
    a,b=map(int,input().split())
    
    total=total-hashmap[a]*a+hashmap[a]*b
    hashmap[b]+=hashmap[a]
    hashmap[a]=0
    print(total)

Submission status: Accepted

Solution code:
n = int(input())
alist = list(map(int, input().split(" ")))
q = int(input())

master = [0 for i in range(100001)]
total = sum(alist)

for a in alist:
  master[a] += 1
for i in range(q):
  b,c = map(int, input().split(" "))
  d = master[b]
  master[b] = 0
  master[c] += d
  total -= b*d
  total += c*d
  print(total)

Submission status: Accepted

Solution code:
N=int(input())
Ax = map(int,input().split())
Q=int(input())

t=[0]*(10**5+1)
s = 0
for a in Ax:
    t[a] += 1
    s += a

for _ in range(Q):
    b,c=map(int,input().split())
    s += t[b]*c
    s -= t[b]*b
    t[c] += t[b]
    t[b] = 0
    print(s)

Submission status: Accepted

Solution code:
import numpy as np
#from numba import njit

#(N, K) = map(int, input().split())
#A = np.array(list(map(int, input().split())))
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC = []
for _ in range(0,Q):
    BC += [list(map(int, input().split())),]

M = {}
for n in A:
    M[n] = M.get(n, 0) + 1


#@njit
def solve(N,A,Q,BC,M):
    S = 0
    for (k,v) in M.items():
        S += k*v
    for (b,c) in BC:
        t = M.pop(b,0)
        M[c] = M.get(c,0) + t
        S += (c-b)*t
        print(S)
    return S
        
S = solve(N,A,Q,BC,M)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n = I()
al = list(MI())
q = I()

a = Counter(al)

s = sum(al)
for _ in range(q):
    b, c = MI()
    if b in a.keys():
        v = a.pop(b)
        if c in a.keys():
            a[c] += v
        else:
            a[c] = v
        s += (c - b) * v
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
a_d = {}
for a in A:
    if a in a_d:
        a_d[a] += 1
    else:
        a_d[a] = 1
mysum = sum(A)
#print(a_d)

Q = int(input())
for q in range(Q):
    b, c = map(int,input().split())
    if b in a_d:
        add = a_d[b] 
        #sub = a_d[c]
        mysum = mysum - add*b + add*c
        a_d[b] = 0
        if c in a_d:
            a_d[c] += add
        else:
            a_d[c] = add
    print(mysum)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())

c = collections.Counter(A)

ans = 0

for k, v in c.items():
    ans += k * v

BC = [map(int, input().split(' ')) for q in range(Q)]

for i in range(Q):
    B, C = BC[i]
    sabun = 0
    if B in c.keys():
        poped_val = c.pop(B)
        if C not in c.keys():
            c[C] = 0
        c[C] += poped_val
        sabun = C * poped_val - B * poped_val
    ans += sabun
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
an = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

# an -> dict
dic = {}
for a in an:
    dic[a] = 1 if a not in dic else dic[a] + 1
sm = sum(k*dic[k] for k in dic)

for i in range(q):
    b, c = bc[i]
    if b in dic:
        sm -= b * dic[b]
        sm += c * dic[b]
        if c in dic:
            dic[c] += dic[b]
        else:
            dic[c] = dic[b]
        del dic[b]
    print(sm)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = Counter([int(_) for _ in input().split()])
Q = int(input())

operates = [tuple(map(int, input().split())) for _ in range(Q)]
result = 0
for k, n in A.items():
  result += k * n

for b, c in operates:
  n_b = A.get(b, 0)
  if n_b > 0:
    A[b] = 0
    A[c] += n_b
    result -= b * n_b
    result += c * n_b
  print(result)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
d = Counter(A)
Q = int(input())

s = sum(map(lambda k: k * d[k], d))
for i in range(Q):
  B, C = [int(x) for x in input().split()]

  s += (C - B) * d[B]
  d[C] = d.get(C, 0) + d[B]
  d[B] = 0
  
  print(s)

Submission status: Accepted

Solution code:
# D
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
a = Counter(a)
# print(a, sum_a)
for i in range(q):
    # print(a)
    # print(bc[i][0], bc[i][1], sum_a)
    num = a[bc[i][0]]*bc[i][1]
    sum_a = sum_a - (a[bc[i][0]] * bc[i][0]) + num

    a[bc[i][1]] += a[bc[i][0]]
    a[bc[i][0]] = 0
    print(sum_a)

Submission status: Accepted

Solution code:
import collections


N = int(input())
A = list(map(int,input().split()))
Q = int(input())
c = collections.Counter(A)
ans = sum(A)
for i in range(Q):
    B,C = list(map(int,input().split()))
    ans = ans + c[B]*(C-B)
    c[C] += c[B]
    c[B] = 0
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
m={}
s=0
for i in input().split():
    i=int(i)
    x=m.get(i,0)
    m[i]=x+1
    s+=i
q=int(input())
for i in range(q):
    b,c=[int(i) for i in input().split()]
    x=m.get(b,0)
    y=m.get(c,0)
    m[b]=0
    m[c]=x+y
    s=s-(b*x)+(c*x)
    print(s)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    opeList = []

    for _ in range(Q):
        b, c = map(int, input().split())

        opeList.append([b, c])
    
    bucket = [0] * (10**5 + 1)
    sumA = sum(A)

    for num in A:
        bucket[num] += 1
    
    for ope in opeList:
        tmp = bucket[ope[0]]
        bucket[ope[0]] = 0
        bucket[ope[1]] += tmp
        sumA = sumA - ope[0] * tmp + ope[1] * tmp
        print(sumA)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def _calc_sum(cache):
    sum_value = 0
    for v, indices in cache.items():
        sum_value += v * len(indices)
    return sum_value


def _main(N, A_list, Q, BC_list):
    cache = {}
    for i, a in enumerate(A_list):
        cache.setdefault(a, []).append(i)

    sum_value = _calc_sum(cache)

    for b, c in BC_list:
        indices = cache.get(b, [])
        cache[b] = []
        sum_value -= b * len(indices)
        cache.setdefault(c, []).extend(indices)
        sum_value += c * len(indices)
        print(sum_value)


def _entry():
    N = int(input())
    A_list = list(map(int, input().split()))
    Q = int(input())
    BC_list = []
    for i in range(Q):
        B, C = map(int, input().split())
        BC_list.append((B, C))
    _main(N, A_list, Q, BC_list)


if __name__ == "__main__":
    _entry()

Submission status: Accepted

Solution code:
n = int(input())
al = list(map(int, input().split()))
q = int(input())
bl = []
cl = []
for i in range(q):
    b,c = map(int, input().split())
    bl.append(b)
    cl.append(c)

shoki = sum(al)

dic = {}
for i in al:
    if i in dic:
        dic[i] += 1
    else:
        dic[i] = 1


for i in range(q):
    b = bl[i]
    c = cl[i]
    if b in dic:
        bcount = dic.pop(b)
    else:
        bcount = 0
    if c in dic:
        dic[c] += bcount
    else:
        dic[c] = bcount
    shoki += (c - b)*bcount
    print(shoki)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

from collections import defaultdict
d = defaultdict(int)
S = 0
for a in A:
   d[a] += 1
   S += a

for _ in range(Q):
   b, c = map(int, input().split())
   S += d[b] * (c - b)
   print(S)
   d[c] += d[b]
   d[b] = 0

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = [int(x) for x in input().split()]
d = Counter(A)
Q = int(input())

def sum_from_counter(d):
  return sum(map(lambda k: k * d[k], d))

s = sum(map(lambda k: k * d[k], d))
for i in range(Q):
  B, C = [int(x) for x in input().split()]
  d[C] = d.get(C, 0) + d[B]
  s += (C - B) * d[B]
  d[B] = 0
  print(s)

Submission status: Accepted

Solution code:
import numpy as np
import math
import scipy as sp
import queue
import collections

MOD = 10 ** 9 + 7
INF = 10 ** 9

def main(kwargs):
    n = kwargs["n"]
    A = kwargs["A"]
    q = kwargs["q"]
    B = kwargs["B"]
    C = kwargs["C"]
    cnt = dict(collections.Counter(A))
    res = [sum(A)]

    for i in range(q):
        if B[i] in cnt.keys():
            res.append(res[-1] + (C[i] - B[i]) * cnt[B[i]])

            if C[i] in cnt.keys():
                cnt[C[i]] += cnt[B[i]]

            else:
                cnt[C[i]] = cnt[B[i]]

            cnt[B[i]] = 0

        else:
            res.append(res[-1])

    res = "\n".join([str(i) for i in res[1:]])
    return res

if __name__ == "__main__":
    kwargs = {}

    cin = input().split()
    kwargs["n"] = [int(i) for i in cin][0]

    cin = input().split()
    kwargs["A"] = [int(i) for i in cin]

    cin = input().split()
    kwargs["q"] = [int(i) for i in cin][0]

    kwargs["B"] = []
    kwargs["C"] = []
    for i in range(kwargs["q"]):
        cin = input().split()
        b, c = [int(i) for i in cin]
        kwargs["B"].append(b)
        kwargs["C"].append(c)

    cout = main(kwargs)
    print(cout)

Submission status: Accepted

Solution code:
n = int(input())
nums = list(map(int, input().split()))
d = [0 for _ in range(10 ** 5 + 10)]
for k in nums:
	d[k] += 1

ans = sum(nums)

q = int(input())
for _ in range(q):
	query = list(map(int, input().split()))
	k = d[query[0]]
	if k >= 1:
		ans += (query[1] - query[0]) * k
		d[query[0]] = 0 
		d[query[1]] += k
	print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()

n= readInt()
a = readInts()
q = readInt()
bc = []
for i in range(q):
	bc.append(readInts())

s = sum(a)
d = defaultdict(int)
for i in a:
	d[str(i)]+=1
for i in bc:
	t = d[str(i[0])]
	d[str(i[0])]=0
	d[str(i[1])]+=t
	s=s-t*i[0]+t*i[1]
	print(s)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    asum = sum(a)
    ac = Counter(a)
    acl = defaultdict(int)
    for ae in ac:
        acl[ae] = ac[ae]

    for _ in range(q):
        b, c = map(int, input().split())
        rmed = acl[b]
        acl[c] += rmed
        acl[b] = 0
        asum -= b * rmed
        asum += c * rmed
        print(asum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
la = list(map(int, input().split()))
s = sum(la)
d = dict(Counter(la))

q = int(input())
for _ in range(q):
    b,c = map(int, input().split())
    if b in d:
        nb = d.pop(b)
    else:
        nb = 0
    delta = (c-b)*nb
    s += delta
    print(s)
    if nb > 0:
        if c in d:
            d[c] += nb
        else:
            d[c] = nb

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = input().split()
q = int(input())
counter = Counter(a)
total = 0
for k, v in counter.items():
    total += int(k) * v
for _ in range(q):
    b, c = input().split()
    if counter.get(b):
        total = total - int(b) * counter.get(b) + int(c) * counter.get(b)
        if counter.get(c):
            counter[c] = counter.get(b) + counter.get(c)
        else:
            counter[c] = counter.get(b)
        counter[b] = 0
    print(total)

Submission status: Accepted

Solution code:
#: Author - Soumya Saurav
import sys,io,os,time
from collections import defaultdict
from collections import OrderedDict
from collections import deque
from itertools import combinations
from itertools import permutations
import bisect,math,heapq
alphabet = "abcdefghijklmnopqrstuvwxyz"

input = sys.stdin.readline

########################################
n = int(input())
arr = list(map(int , input().split()))
q = int(input())
m = defaultdict(int)
for i in arr:
	m[i]+=1
ss = sum(arr)
for ii in range(q):
	b , c = map(int , input().split())
	temp = m[b]
	del m[b]
	m[c] += temp
	ss = ss - b*temp + c*temp
	print(ss)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b, c = zip(*[list(map(int, input().split())) for i in range(q)])

cnt = [0] * (10**5+10)

for i in range(n):
    cnt[a[i]] += 1

s = 0
for i, x in enumerate(cnt):
    s += i * x

for i in range(q):
    s -= cnt[b[i]] * b[i]
    s += cnt[b[i]] * c[i]
    cnt[c[i]] += cnt[b[i]]
    cnt[b[i]] = 0
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
q = int(input())
b,c = [0]*q,[0]*q
for i in range(q):
  b[i],c[i] = map(int,input().split())
numdic = {}
for i in range(n):
  if a[i] in numdic:
    numdic[a[i]] += 1
  else:
    numdic[a[i]] = 1
sum = 0
for x in numdic:
  sum += x*numdic[x]
for i in range(q):
  if b[i] in numdic:
    sum += (c[i]-b[i]) * numdic[b[i]]
    if c[i] in numdic:
      numdic[c[i]] += int(numdic[b[i]]) 
    else:  
      numdic[c[i]] = int(numdic[b[i]])
    del numdic[b[i]]
  print(sum)

Submission status: Accepted

Solution code:
n = int(input())
d = {}
for a in list(map(int, input().split())):
    if a not in d:
        d[a] = 0
    d[a] += 1
r = sum(k*d[k] for k in d.keys())

q = int(input())
for _ in range(q):
    b,c = map(int, input().split())
    if b not in d:
        pass
    elif c not in d:
        d[c] = d[b]
        r = r - b*d[b] + c*d[c]
    else:
        d[c] += d[b]
        r = r - b*d[b] + c*d[b]
    d[b] = 0
    print(r)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

A = list(map(int, input().split()))

dic = Counter(A)

Q = int(input())

res = sum(A)

for i in range(Q):
    B, C = map(int, input().split())
    res = res +C*dic[B] - B*dic[B]
    dic[C] += dic[B]
    dic[B] = 0
    print(res)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
def main():
    N = int(input())
    MAX = 10 ** 15
    A = [int(i) for i in input().split()]
    dict_num = {}
    num_sum = 0
    for i in range(N):
        if dict_num.get(A[i]) is None:
            dict_num[A[i]] = 1
        else:
            dict_num[A[i]] += 1
        num_sum += A[i]
    Q = int(input())
    for i in range(Q):
        b, c = map(int, input().split())
        if dict_num.get(b) is None:
            print(num_sum)
        elif dict_num[b] == 0:
            print(num_sum)
        else:
            num_sum += (c - b) * dict_num[b]
            print(num_sum)
            if dict_num.get(c) is None:
                dict_num[c] = dict_num[b]
            else:
                dict_num[c] += dict_num[b]
            dict_num[b] = 0



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

n=int(input())
a=list(map(int,input().split()))
q=int(input())

cnt_dict=collections.Counter(a)
sum=sum(a)

for i in range(q):
    b,c=map(int,input().split())
    cnt=cnt_dict[b]
    sum=sum-b*cnt+c*cnt
    cnt_dict[b]=0
    cnt_dict[c]+=cnt
    print(sum)

Submission status: Accepted

Solution code:
from collections import Counter
import numpy as np

N = int(input())
A = list(map(int, input().split()))
Q = int(input())

d = dict(Counter(A))
ans = sum(A)
for i in range(Q):
    b, c = map(int, input().split())
    
    if(b not in d):
        d[b] = 0
    if(c not in d):
        d[c] = 0
    
    if(b >= c):
        n = d[b]*(c-b)
    else:
        n = d[b]*(c-b)
        
    ans += n
    
    if(c in d):
        d[c] += d[b]
    else:
        d[c] = d[b]
    d[b] = 0
    
    print(ans)

Submission status: Accepted

Solution code:

N=int(input())
A=list(map(int,input().split()))
Q=int(input())

arg=[0]*(100005)
for a in A:
    arg[a]+=1
ans=sum(A)
for _ in range(Q):
    a,b=map(int,input().split())
    ans+=arg[a]*(b-a)
    print(ans)
    arg[b]+=arg[a]
    arg[a]=0

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
d=[0]*100001
for i in a:
    d[i-1]+=1
s=0
for num,i in enumerate(d):
    s+=i*(num+1)

bb=[]
cc=[]
for i in range(q):
    b,c=map(int,input().split())
    bb.append(b)
    cc.append(c)

for b,c in zip(bb,cc):
    k=d[b-1]
    s+=(c-b)*k
    d[b-1]=0
    d[c-1]+=k

    print(s)

Submission status: Accepted

Solution code:
#%%
N = int(input())
L = [int(i) for i in input().split()]
Q = int(input())
order = [[] for _ in range(Q)]

for i in range(Q):
    order[i] = [int(i) for i in input().split()]
#%%
cnt = {}
for i in L:
    if i in cnt:
        cnt[i] += 1
        
    else:
        cnt[i] = 1

ans = [sum(L)]
for i in order:
    if i[0] not in cnt:
        print(ans[-1])
        continue
    temp = cnt[i[0]] * (i[1] - i[0])
    ans.append(temp + ans[-1])
    print(ans[-1])
    
    if i[1] in cnt:
        cnt[i[1]] += cnt[i[0]]
    else:
        cnt[i[1]] = cnt[i[0]]

    del cnt[i[0]]

Submission status: Accepted

Solution code:
def sum_dict(d, sum, b, c):
    val = 0
    if b in d:
        val = d[b]
        sum -= (b * val)
        del d[b]
        d[c] = d.get(c, 0) + val
        sum += (c * val)
    return sum, d
    
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in a:
    d[i] = d.get(i, 0) + 1
s = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s, d = sum_dict(d, s, b, c)
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
ali = list(map(int, input().split()))
q = int(input())

opelates = []
for _ in range(q):
    opelates.append(list(map(int, input().split())))

numCntList = [0 for _ in range(10**5+1)]
for num in ali:
    numCntList[num] += 1
total = sum(ali)

for op in opelates:
    pre = op[0]
    nex = op[1]
    preCnt = numCntList[pre]
    if preCnt >= 1:
        numCntList[pre] = 0
        numCntList[nex] += preCnt
        total += (nex-pre)*preCnt
    print(total)

Submission status: Accepted

Solution code:
def main():
    import collections

    N = int(input())
    A_s = list(map(int, input().split()))
    Q = int(input())

    summ = sum(A_s)
    CNT_A = collections.Counter(A_s)


    for i in range(Q):
        before, after = map(int, input().split())
        
        tmp_cnt = CNT_A[before]
        
        if (tmp_cnt > 0):
            tmp_before = CNT_A[before] * (after - before)
            summ += tmp_before

            N_before=CNT_A[before]

            del CNT_A[before]
            N_after = CNT_A[after]
            
            if (N_after > 0):
                CNT_A[after] = N_after + N_before
            else:
                CNT_A[after] = N_before
            
        
        print(summ)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[];C=[]
for i in range(Q):
    b,c=map(int,input().split())
    B.append(b);C.append(c)
d={}
for a in A:
    if a not in d:
        d[a]=1
    else:
        d[a]+=1
s=sum(A)
for i in range(Q):
    b = B[i]
    c = C[i]
    if b not in d:
        print(s)
    else:
        if c not in d:
            s=s+(c-b)*d[b]
            print(s)
            d[c] = d[b]
            del d[b]
        else:
            s=s+(c-b)*d[b]
            print(s)
            d[c] += d[b]
            del d[b]

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
q=int(input())
S = [list(map(int, input().split())) for _ in range(q)]
C=Counter(a)
#print(C)
ans=0
for k,v in C.items():
    ans+=k*v
#print(ans)
for i in range(q):
    if S[i][0] in C:
        if C[S[i][0]]>=1:
            ans+=(S[i][1]-S[i][0])*C[S[i][0]]
            C[S[i][1]]+=C[S[i][0]]
            C[S[i][0]]=0
    print(ans)

Submission status: Accepted

Solution code:
import collections 
N=int(input())
A=list(map(int,input().split()))
A_count = collections.Counter(A)
#print(A_count)
Q=int(input())
S=sum(A)
for i in range(Q):
  B,C=map(int,input().split())
  S += (C-B)*A_count[B]
  A_count[C] += A_count[B]
  A_count[B]= 0
  print(S)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(i) for i in input().split()]
q=int(input())
l=[0]*(10**5+1)
s=sum(a)
for i in a:
  l[i]+=1
for i in range(q):
  b,c=map(int,input().split())
  s+=(c-b)*l[b]
  print(s)
  l[c]+=l[b]
  l[b]=0

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    dic1 = {}
    total = 0
    for i in range(n):
        if a[i] in dic1:
            dic1[a[i]] += 1
        else:
            dic1[a[i]] =1
        total += a[i]

    for i in range(q):
        b, c = map(int, input().split())
        if not b in dic1:
            print(total)
            continue
        bcount = dic1[b]
        if bcount == 0:
            print(total)
            continue
        inc = bcount * (c-b)
        if c in dic1:
            dic1[c] += bcount
        else:
            dic1[c] = bcount
        dic1[b] = 0
        total += inc
        print(total)
resolve()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
ls=[0 for i in range(100000)]#O(100000)
S=sum(A)
for i in range(N):#O(100000)
  ls[A[i]-1]+=1
for i in range(Q):#O(100000)
  B,C=map(int,input().split())
  ls[C-1]+=ls[B-1]
  S+=(C-B)*ls[B-1]
  ls[B-1]=0
  print(S)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))

m = [0] * (10 ** 5 + 10)

for i in range(n):
  m[a[i]] += 1

ans = sum(a)
# print(ans)

q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  count = m[b]
  ans -= b * count
  ans += c * count
  m[c] += count
  m[b] = 0
  print(ans)