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 sys
from collections import defaultdict, Counter, deque
from itertools import accumulate, permutations, combinations
from operator import itemgetter
from bisect import bisect_left, bisect_right, bisect
from heapq import heappop, heappush
from fractions import gcd
from math import ceil, floor, sqrt, cos, sin, pi
from copy import deepcopy

# If you use recursive call, uncomment this code
#sys.setrecursionlimit(10**6)

def main():
    N = int(input())
    A = list(map(int, input().split()))
    suma = sum(A)
    A = Counter(A)
    Q = int(input())
    for _ in range(Q):
        b,c = map(int, input().split())
        suma -= A[b]*b
        suma += A[b]*c
        A[c] += A[b]
        A[b] = 0
        print(suma)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

D={}
ans=0
for i in range(n):
    now=A[i]
    ans+=A[i]
    if now in D:
        D[now]+=1
    else:
        D[now]=1
       
    

q=int(input())

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

Submission status: Accepted

Solution code:
num = [0]*100100

n = int(input())
sum = 0
for A in map(int, input().split()):
  num[A] += 1
  sum += A

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

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)]

total = sum(A)
from collections import Counter
counter = Counter(A)

for b, c in BC:
    total += (c-b) * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = int(input())
    A = [int(e) for e in input().split()]
    q = int(input())
    BC = [[int(e) for e in input().split()] for i in range(q)]

    s = sum(A)
    D = Counter(A)
    for bc in BC:
        b, c = bc
        s -= b * D[b]
        s += c * D[b]
        D[c] += D[b]
        D[b] = 0

        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [0] * Q
    C = [0] * Q
    
    for i in range(Q):
        B[i],C[i] = map(int,input().split())
    
    c = [0] * (10 ** 5 + 10)
    
    for i in range(N):
        c[A[i]] += 1
    SUM = sum(A)
    
    for i in range(Q):
        if c[B[i]] == 0:
            print(SUM)
            continue
        SUM -= B[i] * c[B[i]]
        SUM += C[i] * c[B[i]]
        c[C[i]] += c[B[i]]
        c[B[i]] = 0
        print(SUM)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict as dd
from collections import deque as dq
import itertools as it
from math import sqrt, log, log2
from fractions import Fraction

n = int(input())
nums = list(map(int, stdin.readline().split()))
q = int(input())

freq = dd(int)
ssf = 0
for i in nums:
    freq[i]+= 1
    ssf += i

for _ in range(q):
    b, c = map(int, input().split())
    if freq[b] == 0:
        print(ssf)
        continue
    else:
        minus = b*freq[b]
        plus = c*freq[b]
        ssf += (plus - minus)
        freq[c] += freq[b]
        freq[b] = 0
        print(ssf)

Submission status: Accepted

Solution code:
n = int(input())
a = map(int,input().split())
d = dict()
res = 0
for i in a:
  res += i
  if i not in d:
    d[i] = 1
  else:
    d[i] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Acount = Counter(A)
Adic = dict(Acount)
Akey = set(Adic.keys())
M = max(A)
L = [0 for i in range(10**5)]
for i in range(M):
    if i+1 in Akey:
        L[i] = Adic[i+1]
s = 0
for i in range(M):
    s += (i + 1) * L[i]
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * L[b - 1]
    L[c - 1] += L[b - 1]
    L[b - 1] = 0
    print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# import bisect
from collections import Counter, deque, OrderedDict, defaultdict
# from copy import copy, deepcopy # pythonのみ．copyは1次元，deepcopyは多次元．
# from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
# from functools import reduce
# from heapq import heapify, heappop, heappush
# from itertools import accumulate, permutations, combinations, combinations_with_replacement, groupby, product
# import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import statistics # Pythonのみ
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    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())
    
    ans=sum(A)
    l=Counter(A)
    for i in range(Q):
        dif=C[i]-B[i]
        ans+=dif*l[B[i]]
        l[C[i]]+=l[B[i]]
        l[B[i]]=0
        print(ans)



    
resolve()

Submission status: Accepted

Solution code:
import numpy as np


N = int(input())
A_arr = [int(v) for v in input().split()]  
Q = int(input())
sum = np.sum(A_arr)
num_arr = np.zeros(100001, dtype = int)
for a in A_arr:
  num_arr[a] += 1
for i in range(Q):
  Bi, Ci = [int(v) for v in input().split()]   
  replace_num = num_arr[Bi]
  sum += replace_num * (Ci - Bi)
  print(sum)
  num_arr[Ci] += num_arr[Bi]
  num_arr[Bi] = 0

Submission status: Accepted

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

Submission status: Accepted

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

ans = sum(a)
nums = [0]*(10**5+1)
for i in a: nums[i] += 1

for _ in range(q):
  b,c = map(int, input().split())
  if nums[b] > 0:
    ans -= b*nums[b]
    nums[c] += nums[b]
    ans += c*nums[b]
    print(ans)
    nums[b] = 0
  else:
    print(ans)

Submission status: Accepted

Solution code:
import collections

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[]
C=[]
for i in range(Q):
	b,c=list(map(int,input().split()))
	B.append(b)
	C.append(c)

X=collections.Counter(A)

ans=sum(A)
for i in range(Q):
	a=X[B[i]]
	X.subtract({B[i]:a})
	X.update({C[i]:a})
	ans+=a*(C[i]-B[i])
	print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0] * Q
C = [0] * Q

ans = []

Adic = {}
sum = 0
for n in range(N):
	sum += A[n]
	if not A[n] in Adic:
		Adic[A[n]] = 1
	else:
		Adic[A[n]] +=1

for i in range(Q):
	B,C = map(int,input().split())
	if B in Adic:
		sum = sum - B * Adic[B] + C * Adic[B]
		
		if C in Adic :
			Adic[C] += Adic[B]
		else:
			Adic[C] = Adic[B]
		Adic.pop(B)

	ans.append(sum)

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
n = int(input())
alist = [int(s) for s in input().split(" ")]
adict = {}
ans = 0
for a in alist:
  ans += a
  if a in adict:
    adict[a] += 1
  else:
    adict[a] = 1
q = int(input())
bclist = []
for _ in range(q):
  b, c = [int(s) for s in input().split(" ")]
  bclist.append([b, c])

for b, c in bclist:
  if c in adict and b in adict:
    ans += (c - b) * adict[b]
    adict[c] += adict[b]
    del adict[b]
  elif b in adict:
    ans += (c - b) * adict[b]
    adict[c] = adict[b]
    del adict[b]
  print(ans)

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)]

ans=sum(a)

from collections import defaultdict
d = defaultdict(int)

for num in a:
    d[num]+=1

for b,c in bc:
    if d[b]==0:
        print(ans)
        continue
    ans-= b*d[b]
    d[c]+=d[b]
    ans+=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())

from collections import Counter

ca = Counter(a)

ans=sum(a)
for _ in range(q):
    b,c = list(map(int, input().split()))
    
    if b in ca:
        cnt = ca.pop(b)
        ca[c] += cnt

        ans -= b * cnt
        ans += c * cnt
    
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

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

D = defaultdict(int)

for a in A:
    D[a] += 1

ans = sum(A)

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

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n = int(input())
    al = list(map(int, input().split()))
    q = int(input())
    cnt_dic = {}
    ans = 0
    for a in al:
        cnt_dic.setdefault(a,0)
        cnt_dic[a] += 1
        ans += a

    bcl = []
    for _ in range(q):
        b, c = map(int, input().split())
        bcl.append((b,c))


    for bc in bcl:
        b,c = bc
        if b not in cnt_dic:
            print(ans)
            continue
        ans += cnt_dic[b]*(c-b)
        cnt_dic.setdefault(c,0)
        cnt_dic[c] += cnt_dic[b]
        cnt_dic[b] = 0
        print(ans)




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import collections
import math

def main():

    input = sys.stdin.readline

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

    c = collections.Counter(A)

    ans = sum(A)
    ans_list = []

    for _ in range(Q):
        B,C = map(int,input().split())

        B_num = c[B]

        ans = ans - B_num * B
        ans = ans + B_num * C

        c[C] = c[C] + B_num
        c[B] = 0

        ans_list.append(ans)

    for i in ans_list:
        print(i)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    ans = [None]*q
    sm = sum(a)
    dic = {}
    for i in range(n):
        if a[i] in dic:
            dic[a[i]] += 1
        else:
            dic[a[i]] = 1
    for i in range(q):
        b, c = map(int, input().split())
        if b in dic:
            x = dic[b]
            dic[b] = 0
            df = c - b
            sm += df * x
            ans[i] = sm
            if c in dic:
                dic[c] += x
            else:
                dic[c] = x
        else:
            ans[i] = sm
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import defaultdict
ddict = defaultdict(lambda: 0)
for A in a:
    ddict[A] += 1


ans =0
for k,v in dict(ddict).items():
    ans += k*v
# print(ans)
# print(ddict)

for P in p:
    bef = P[0]
    aft = P[1]
#     print(ddict[bef])
    diff = +aft*ddict[bef]- bef*ddict[bef]
    print(ans+diff)
    ans += diff
    ddict[aft] += ddict[bef]
    ddict[bef] = 0
#     print(diff)
#     print(ddict)

Submission status: Accepted

Solution code:
N = int(input())
A = [0 for _ in range(100001)]
a = list(map(int,input().split()))
ans = 0
for i in a:
  A[i] += 1
  ans += i
Q = int(input())
for i in range(Q):
  B,C = map(int,input().split())
  ans += (C -B) * A[B]
  A[C] += A[B]
  A[B] = 0
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    number = int(input())
    numcount = defaultdict(int)
    for x in input().split():
        numcount[int(x)] += 1
    queries = int(input())
    ans = sum(num * count for num, count in numcount.items())
    for _ in range(queries):
        before, after = [int(x) for x in input().split()]
        tmp = numcount[before]
        numcount[before] -= tmp
        numcount[after] += tmp
        ans += (after - before) * tmp
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []
for _ in range(q):
    d, e = map(int, input().split())
    b.append(d)
    c.append(e)
f = {}
for i in range(n):
    try:
        f[a[i]] += 1
    except KeyError:
        f[a[i]] = 1
ans = 0
for i in f.keys():
    ans += i * f[i]
for i in range(q):
    try:
        ss = f[b[i]]
        ans += (c[i] - b[i]) * ss
        if(not(c[i] in f)):
            f[c[i]] = 0
        f[c[i]] += f[b[i]]
        f[b[i]] = 0
        print(ans)
    except KeyError:
        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(A)
#print(c)
total = sum(A)

for _ in range(Q):
    B, C = map(int, input().split())
    total += (C-B)*c[B]
    c[C] += c[B]
    c[B] = 0
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
Q=int(input())
cnt=Counter(A)
for _ in range(Q):
    b,c=map(int,input().split())
    if b in cnt:
        s-=cnt[b]*b
        s+=cnt[b]*c
        print(s)
        if c in cnt:
            cnt[c]+=cnt[b]
            cnt[b]=0
        else:
            cnt[c]=cnt[b]
            cnt[b]=0
    else:
        print(s)

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
#read = sys.stdin.buffer.read

def main():
    N = int(input())
    A = list(map(int, input().split()))
    Asum = sum(A)
    Acount = collections.Counter(A)
    Q = int(input())
    for _ in range(Q):
        B, C = map(int, input().split())
        Bcount = Acount[B]
        Asum += (C - B)*Bcount
        print(Asum)
        Acount[C] += Acount[B]
        Acount[B] -= Acount[B]

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
table = [0 for i in range(10**5+10)]
for i in range(n):
    table[a[i]] += 1

ans = 0
for i in range(len(table)):
    ans += table[i]*i

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
queries = list(list(map(int, input().split())) for _ in range(Q))

dic = dict()
s = 0
for i in range(N):
    s += A[i]
    if A[i] not in dic:
        dic[A[i]] = 1
    else:
        dic[A[i]] += 1
        
for q in range(Q):
    query = queries[q]
    if query[0] in dic:
        num = dic[query[0]]
        s -= num*query[0]
        dic.pop(query[0])
        if query[1] not in dic:
            dic[query[1]] = num
        else:
            dic[query[1]] += num
        s += num*query[1]
    print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

cnt = defaultdict(int)
for a in A:
    cnt[a] += 1
ttl = sum(A)

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    
    if b in cnt:
        occ = cnt.pop(b)
        cnt[c] += occ
        ttl = ttl - b * occ + c * occ
    
    print(ttl)

Submission status: Accepted

Solution code:
import sys
from collections import Counter,defaultdict
imput = sys.stdin.readline

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
ans = sum(A)
A = Counter(A)
for i in range(Q):
    b,c = map(int,input().split())
    tmp = A.pop(b,None)
    if tmp:
        ans += (c-b)*tmp
        print(ans)
        if c in A:
            A[c] += tmp
        else:
            A[c] = tmp

    else:
        print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = [0] * 10 ** 5
for v in a:
    cnt[v-1] += 1

res = [sum(a)]
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    res.append(res[-1] + cnt[b-1] * (c - b))
    cnt[c-1] += cnt[b-1]
    cnt[b-1] = 0

for v in res[1:]:
    print(v)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
m = max(A)
A2 = dict(collections.Counter(A))
#print(A2)
Q = int(input())
#BC = [0] * Q
#for i in range(Q):
#  BC[i] = list(map(int, input().split()))

ans = [0] * (10 ** 5)
for i in range(1, 10 ** 5 + 1):
  if i in A2:
    ans[i - 1] = A2[i]
#print(ans)
now = sum(A)
#print(now)
for i in range(Q):
  b, c = map(int, input().split())
  now += ans[b - 1] * (c - b)
  ans[c - 1] += ans[b - 1]
  ans[b - 1] = 0
  #print(ans)
  print(now)

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(s) for s in input().strip().split()]
q = int(input())

b_list = [0] * q
c_list = [0] * q
for i in range(q):
    b, c = [int(s) for s in input().strip().split()]
    b_list[i] = b
    c_list[i] = c

num_list = [0] * (10**5 + 1)
for i in a_list:
    num_list[i] += 1
num_sum = sum([i * n for i, n in enumerate(num_list)])

for b, c in zip(b_list, c_list):
    num_sum += (c - b) * num_list[b]
    num_list[c] += num_list[b]
    num_list[b] = 0
    print(num_sum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = list(list(map(int, input().split())) for i in range(q))
dic = {}
for i in range(n):
    if a[i] not in dic.keys():
        dic[a[i]] = 1
    else:
        dic[a[i]] += 1
su = sum(a)
for i in range(q):
    if b[i][0] not in dic.keys():
        pass
    else:
        su += (b[i][1]-b[i][0])*dic[b[i][0]]
        if b[i][1] not in dic.keys():
            dic[b[i][1]] = 0
        dic[b[i][1]] += dic[b[i][0]]
        dic[b[i][0]] = 0
    print(su)

Submission status: Accepted

Solution code:
n = int(input())
sum = 0
nums = dict()
for num in input().split():
	sum += int(num)
	nums[num] = nums.get(num, 0) + 1
q = int(input())
for v in range(q):
	bi, ci = [vi for vi in input().split()]
	count = nums.get(bi, 0)
	change = (int(ci) - int(bi)) * count
	sum += change
	print(sum)
	if count != 0:
		nums[bi] = 0
	nums[ci] = nums.get(ci, 0) + count

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
total = sum(a)
d = defaultdict(int)

for i in a:
    d[i] += 1

q = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
l =  list (map (int, input().strip().split()))
d={}
s = 0
for i in range(n):
    s+=l[i]
    if l[i] not in d:
        d[l[i]]  = 1 
    else:
        d[l[i]]+=1 
q = int(input())
for i in range(q):
    l2 =  list (map (int, input().strip().split()))
    b = l2[0]
    c = l2[1]
    x = 0
    y = 0
    if b not in d:
        x = 0
    else:
        x = d[b]
    if c not in d:
        y = 0
    else:
        y = d[c]
    test1 =  (c-b)*x
    s = s+test1
    print(s)
    d[b]=0
    d[c] = x+y

Submission status: Accepted

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

from collections import defaultdict

dic=defaultdict(int)
for i in range(N):
    dic[A[i]]+=1

summ=sum(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
Q=int(sys.stdin.readline().strip())

KOSUU=Counter(A)
total=sum(A)
for _ in range(Q):
    b,c=map(int, sys.stdin.readline().split())
    total=total-b*KOSUU[b]+c*KOSUU[b]
    print total
    KOSUU[c]+=KOSUU[b]
    KOSUU[b]=0

Submission status: Accepted

Solution code:
import numpy as np

n= int(input())
a = np.array(list(map(int, input().split())))
q = int(input())
actions = []
for i in range(q):
  actions.append(list(map(int, input().split())))

numbers = [0]*10**5
ans = a.sum()
a_unique, a_freq = np.unique(a,return_counts=True)
for i in range(len(a_unique)):
  numbers[a_unique[i]-1] = a_freq[i]

for action in actions:
  if numbers[action[0]-1] != 0:
    tmp = numbers[action[0]-1]
    numbers[action[0]-1] = 0
    numbers[action[1]-1] += tmp
    ans = ans -tmp*(action[0]-action[1])

  print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a0=input().split()

sum0=0
al=[0 for i in range(100001)]

for i in range(n):
  al[int(a0[i])]+=1
  sum0+=int(a0[i])

q=int(input())

for i in range(q):
  b0=input().split()
  zen=int(b0[0])
  go=int(b0[1])
  changes=al[zen]
  al[zen]=0
  al[go]+=changes
  sum0+=changes*(go-zen)
  print(sum0)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[tuple(map(int,input().split())) for _ in range(q)]
d={}
for ai in a:
    if ai not in d:
        d[ai]=0
    d[ai]+=1
# print(d)

ans=0
for key in d:
    ans+=key*d[key]

for bi,ci in bc:
    if bi in d:
        tmp=d[bi]
        d[bi]=0
        ans-=bi*tmp
        if ci not in d:
            d[ci]=0
        d[ci]+=tmp
        ans+=ci*tmp
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = tuple(map(int, input().split(' ')))
counter = Counter(A)
Q = int(input())
s = sum(A)
for _ in range(Q):
    B, C = map(int, input().split(' '))
    diff = (C - B) * counter[B]
    s += diff
    counter[C] += counter[B]
    counter[B] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
num = [0] * (10 ** 5 + 1)
for a in A:
    num[a] += 1

Q = int(input())
for _ in range(Q):
    b, c = map(int, sys.stdin.readline().split())
    total -= b * num[b]
    total += c * num[b]
    num[c] += num[b]
    num[b] = 0
    print(total)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
a=lmp()
count=[0]*(10**5+1)
c=Counter(a).items()
s=sum(a)
q=int(input())

for p in c:
    count[p[0]]+=p[1]
for i in range(q):
    b,c=mp()
    s+=(c-b)*count[b]
    count[c]+=count[b]
    count[b]=0
    print(s)

Submission status: Accepted

Solution code:
import math
import itertools
import collections
import bisect
import heapq

def IN(): return int(input())
def sIN(): return input()
def MAP(): return map(int,input().split())
def LMAP(): return list(map(int,input().split()))
def TATE(n): return [input() for i in range(n)]
MOD = 10**9 + 7


n = IN()
a = LMAP()
q = IN()
ans = sum(a)
dic = {}

for i in a:
  if i not in dic:
    dic[i] = 1
  else:
    dic[i] += 1

for i in range(q):
  b,c = MAP()
  if b not in dic:
    print(ans)
  else:
    ans -= (b-c) * dic[b]
    if c in dic:
      dic[c] += dic[b]
      dic.pop(b)
    else:
      dic[c] = dic.pop(b)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter(A)

baseline = sum(k*v for k, v in counter.items())
#print(baseline)

for i in range(Q):
    b, c = map(int, input().split())
    n = counter.pop(b, 0)
    baseline += n * (c - b)
    counter[c] += n
    print(baseline)

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a_list = list(map(int, input().split()))
    q = int(input())
    bcs = [map(int, input().split()) for _ in range(q)]
    bs, cs = [list(i) for i in zip(*bcs)]
    cnter = Counter(a_list)
    s = sum(a_list)
    for i in range(q):
        m = cnter[bs[i]]
        cnter[bs[i]] = 0
        cnter[cs[i]] += m
        s += m * cs[i] - m * bs[i]
        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
s = sum(A)
nu = [0 for _ in range(10**5+1)]
for i in range(N):
    nu[A[i]] += 1
for j in range(Q):
    B,C = map(int,input().split())
    s += (C-B)*nu[B]
    nu[C] += nu[B]
    nu[B] = 0
    print(s)

Submission status: Accepted

Solution code:
n=int(input())
aa=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
ans=sum(aa)
ind=[0]*(10**5)
for i in aa:
  ind[i-1]+=1
for b,c in bc:
  ans+=(c-b)*(ind[b-1])
  ind[c-1]+=ind[b-1]
  ind[b-1]=0  
  print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

n = int(input())
A = list(map(int, input().split()))
q = int(input())
readline = sys.stdin.readline
BC = [[int(i) for i in readline().split()] for _ in range(q)]

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

#MAX_N = 10**5+5
#l_conv = [0]*MAX_N
#
#for b,c in BC:
#    l_conv[b] = c

ans = []
su = sum(A)

for b,c in BC:
    if b in d:
        su = su - b*d[b] + c*d[b]
        d[c] = d.get(c, 0) + d[b]
        d.pop(b)
        ans.append(su)
    else:
        ans.append(su)

print(*ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]

import collections
sum_temp = sum(A)
c = collections.Counter(A)
for q in range(Q):
  B = BC[q][0]
  C = BC[q][1]
  sum_temp += c[B]*(C-B)
  c[B],c[C] = 0,c[B]+c[C]
  print(sum_temp)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
As = map(int, input().split())

counter = Counter(As)

sum = 0
for key in counter:
    sum += int(key) * counter[key]

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    if b in counter:
        counter[c] += counter[b]
        sum += counter[b] * (c-b)
        del counter[b]

    print(sum)

Submission status: Accepted

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

dic = {}
sum = 0
for i in a:
	sum += i
	if i in dic:
		dic[i] += 1
	else:
		dic[i] = 1

q = int(input())

ans = []
for i in range(q):
	b, c = map(int, input().split())
	if b in dic:
		if c in dic:
			sum += dic[b]*c - dic[b]*b
			dic[c] += dic[b]
			dic.pop(b)
			ans.append(sum)
		else:
			dic[c] = dic[b]
			sum += dic[c]*c - dic[b]*b
			dic.pop(b)
			ans.append(sum)

	else:
		ans.append(sum)

for i in ans:
	print(i)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
dic = Counter(a)
q = int(input())
bs = []
cs = []
for _ in range(q):
    b, c = map(int, input().split())
    bs.append(b)
    cs.append(c)

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

for i in range(q):
    b = bs[i]
    c = cs[i]
    b_num = dic.get(b, 0)
    ans = ans + (c - b) * b_num
    dic[c] = dic.get(c, 0) + dic.get(b, 0)
    dic[b] = 0
    print(ans)