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:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int,input().split())) for _ in range(q)]

all_sum  = sum(a)

cnt = {}
for i in a:
    if i not in cnt:
        cnt[i] = 0
    cnt[i] += 1

for (b, c) in query:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c]=0 
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)

Submission status: Accepted

Solution code:
from collections import defaultdict

N=int(input())
A=list(map(int,input().split()))
count=defaultdict(int)
ans=0
for i in range(N):
    count[A[i]]+=1
    ans+=A[i]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    ans = sum(a)
    q = int(input())
    #d = dict((x,a.count(x)) for x in set(a))
    d = Counter(a)
    for _ in range(q):
        b, c = map(int, input().split())
        # cの値がない場合の対処
        d.setdefault(c, 0)
        # bの値がない場合の対処
        d[c] = d.get(c) + d.get(b, 0)
        # 差分はbの個数 * (c-b) 
        diff = d.get(b, 0) * (c-b)
        d[b] = 0
        ans += diff
        print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import defaultdict

def II(): return int(input())
def MII(): return map(int, input().split())
def LII(): return list(map(int, input().split()))

def main():
    N = II()
    A = LII()
    Q = II()

    ans = sum(A)
    d = defaultdict(int)
    for a in A:
        d[a] += 1

    for _ in range(Q):
        B, C = MII()
        if d[B] > 0:
            d[C] = d[C] + d[B]
            ans += (C - B) * d[B]
            d[B] = 0

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
L=[0]*(100001)
#何回その数字が出てきたかのリスト
ans=0
for a in A:
  L[a]+=1
  #aが出てきた数（2回出てきたら2になる）
  ans+=a
Q=int(input())
for i in range(Q):
  B,C=map(int, input().split())
  key=L[B]
  L[C]+=key
  ans+=key*(C-B)
  L[B]=0
  print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
k = int(input())
s = sum(arr)
d = {}
for i in arr:
    if i in d:
        d[i] += 1
    else:
        d[i] = 1
for _ in range(k):
    v = 0
    a,b = map(int, input().split())
    if a not in d:
        print(s)
        continue
    s += (b-a) * d[a]
    if b in d:
        d[b] += d[a]
    else:
        d[b] = d[a]
    print(s)
    del d[a]

Submission status: Accepted

Solution code:
sum=0
dic={}
n=int(input())
lis=input()
lis=lis.split(' ')
def con(a,b):
    if b in dic:
        dic[b]=dic[b]+dic[a]
    else:
        dic[b]=dic[a]
    del dic[a]
for i in lis:
    sum=sum+int(i)
    if int(i) in dic:
        dic[int(i)]=dic[int(i)]+1
    else:
        dic[int(i)]=1
#print(dic)
#print(sum)
q=int(input())
for i in range(0,q):
    que=input()
    que=que.split()
    que[0]=int(que[0])
    que[1]=int(que[1])
    if que[0] in dic:
        if que[0]>que[1]:
            sum=sum-(que[0]-que[1])*dic[que[0]]
            con(que[0],que[1])
        else:
            sum=sum+(que[1]-que[0])*dic[que[0]]
            con(que[0],que[1])
    print(sum)

Submission status: Accepted

Solution code:
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())

num_dict = dict()
for i in a:
    if i in num_dict.keys():
        num_dict[i] += 1
    else:
        num_dict[i] = 1

ans = 0       
for k, v in num_dict.items():
  ans += k*v
 
for i in range(q):
    if b[i] in num_dict:
        if c[i] in num_dict:
            ans += (c[i] - b[i]) * num_dict[b[i]]
            num_dict[c[i]] += num_dict.pop(b[i])
        else:
            ans += (c[i] - b[i]) * num_dict[b[i]]
            num_dict[c[i]] = num_dict.pop(b[i])
    #print(num_dict)
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
d=(10**5+100)*[0]
res=sum(A)
for x in A:
    d[x]+=1
for i in range(Q):
    b,c=map(int,input().split())
    res+=d[b]*(c-b)
    d[c]+=d[b]
    d[b]=0
    print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
# q=int(input())
L=[0]*(100001)
s=sum(a)

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

q= int(input())
for _ in range(q):
    b, c = map(int,input().split())
    L[c] += L[b]
    s+= L[b]*(c-b)
    L[b]=0
    print(s)
# b=[]
# c=[]
# for i in range(q):
#     d,e=input().split()
#     b.append(int(d))
#     c.append(int(e))


# if q >= len(b):
#     for j in range(q):
#         for i in range(len(b)):
#             if q < len(b):
#                 if a[j]==b[i]:
#                     a[j]=c[i]
# else:
#     for i in range(len(b)):
#         for j in range(q):
#             if a[i] == b[j]:
#                 a[i]=c[j]
#         # elif q < len(b):
#         #     if a[i] == b[i]:
#         #         a[i]=c[j]
#         #         if a[-1] ==b[j]:
#         #             a[-1]=c[i]
#         print(sum(a))



# # print(a)
# # print(a)
# # print(b)
# # print(c)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
A = list(map(int,input().split()))
q = int(input())
ar = np.zeros(10**5+1)
for i in A:
    ar[i] += 1
ans = np.sum(A) 
for _ in range(q):
    b,c = map(int,input().split())
    ans = ans+ar[b]*(c-b)
    ar[c] += ar[b]
    ar[b] = 0
    print(int(ans))

Submission status: Accepted

Solution code:
def solve(A,N,Q,BC):
    A_dict = {}
    for a in A:
        if a in A_dict:
            A_dict[a] += 1
        else:
            A_dict[a] = 1

    ans_list = [sum(A)]
    for b,c in BC:
        diff = 0
        if b in A_dict:
            diff += (c-b) * A_dict[b]
            if c in A_dict:
                A_dict[c] += A_dict[b]
            else:
                A_dict[c] = A_dict[b]
            A_dict.pop(b)
        ans_list.append(ans_list[-1] + diff)

    return ans_list[1:]

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

    ans = solve(A,N,Q,BC)
    for i in range(Q):
        print(ans[i])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
C = sum(A)
Z = {}
for n in range(N):
    Z[A[n]] = 0
for n in range(N):
    Z[A[n]] += 1
D = []
Q = int(input())
for q in range(Q):
    x, y = map(int, input().split())
    if x in Z:
        C = C - x*Z[x]
        C = C + y*Z[x]
        D.append(C)
        if y in Z:
            Z[y] += 1*Z[x]
        else:
            Z[y] = Z[x]
        Z.pop(x)
    else:
        D.append(C)
for d in D:
    print(d)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
C = sum(A)
Z = {}
for n in range(N):
    Z[A[n]] = 0
for n in range(N):
    Z[A[n]] += 1
D = []
Q = int(input())
for q in range(Q):
    x, y = map(int, input().split())
    if x in Z:
        C = C - x*Z[x]
        C = C + y*Z[x]
        D.append(C)
        if x == y:
            continue
        if y in Z:
            Z[y] += 1*Z[x]
        else:
            Z[y] = Z[x]
        Z.pop(x)
    else:
        D.append(C)
for d in D:
    print(d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()
	Q = inputInt()

	kanninngu = {}
	goukei = sum(A)
	for i,val in enumerate(A):
		if val in kanninngu:
			kanninngu[val] += 1
		else:
			kanninngu[val] = 1

	for i in range(Q):
		B,C = inputMap()

		if B in kanninngu:
			pass
		else:
			print(goukei)
			continue
			
		tmp = kanninngu[B]
		tmp_sum = B * tmp

		moto = 0
		if C in kanninngu:
			moto = kanninngu[C]

		kanninngu[B] = 0
		kanninngu[C] = tmp + moto
		c_sum = C * tmp

		goukei = goukei + (c_sum - tmp_sum)
		print(goukei)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    B = [list(map(int,input().split())) for _ in range(Q)]
    dict = {}

    for i in range(1,10**5+1):
    #for i in range(1,6):
        dict[i] = 0

    for i in range(N):
        dict[A[i]] += 1

    sum = 0
    for i in range(1,10**5+1):
        #for i in range(1,6):
        if dict[i] != 0:
            sum += dict[i]*i

    for i in range(Q):
        sum = sum +(dict[B[i][0]]*B[i][1] - dict[B[i][0]]*B[i][0])

        dict[B[i][1]] += dict[B[i][0]]
        dict[B[i][0]] = 0
        #print(dict)
        print(sum)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    A = rl()
    counts = dd(int)
    total  = 0
    for a in A:
        total += a
        counts[a] += 1

    for _ in range(ri()):
        x, y = rl()
        rem = counts[x]
        total += (y - x) * rem
        counts[x] = 0
        counts[y] += rem
        print (total)






mode = 's'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()

Submission status: Accepted

Solution code:
#abc171d
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
d=(10**5+100)*[0]
res=sum(A)
for x in A:
 d[x]+=1
for i in range(Q):
 b,c=map(int,input().split())
 res+=d[b]*(c-b)
 d[c]+=d[b]
 d[b]=0
 print(res)

Submission status: Accepted

Solution code:
import collections

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

bc = [map(int, input().split()) for _ in range(Q)]
b, c= [list(i) for i in zip(*bc)]

count = collections.Counter(A)
# count.append([0] * 10)
sumA = sum(A)

for iter in range(Q):
    sumA += count[b[iter]]*(c[iter]- b[iter])
    count[c[iter]] += count[b[iter]] 
    count[b[iter]] = 0
    print(sumA)

Submission status: Accepted

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

cnt = [0] * 10**6
tot = sum(a_list)

for i in range(n):
    cnt[a_list[i]] += 1
#print(cnt)

for j in range(q):
    tot += cnt[change_list[j][0]] * (change_list[j][1]-change_list[j][0])
    cnt[change_list[j][1]] += cnt[change_list[j][0]]
    cnt[change_list[j][0]] = 0
    print(tot)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
sum_a = sum(a)
count_a = Counter(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    tmp = count_a[b]
    new = {c : tmp}
    count_a.update(new)
    del count_a[b]
    sum_a = sum_a - b * tmp + c * tmp
    print(sum_a)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
num_dic={}
for i in A:
    if i not in num_dic:
        num_dic[i]=1
    else:
        num_dic[i]+=1
Q=int(input())
for i in range(Q):
    b,c=list(map(int,input().split()))
    if b in num_dic:
        count=num_dic[b]
        d=(c-b)*count
        print(goukei+d)
        goukei+=d
        if c in num_dic:
            num_dic[c]+=num_dic[b]
        else:
            num_dic[c]=num_dic[b]
        num_dic[b] = 0
    else:print(goukei)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
di = Counter(A)
S = sum(A)
for q in range(int(input())):
    b, c = map(int, input().split())
    di[c] += di[b]
    S += (c-b) * di[b]
    di[b] = 0
    print(S)

Submission status: Accepted

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

from collections import Counter
z = Counter(a)

sum = sum(a)
for i in range(q):
    try:
        rev = z.pop(u[i][0])
        sum+=(u[i][1]-u[i][0])*rev
        print(sum)
        if u[i][1] in z:
            z[u[i][1]]+=rev
        else:
            z[u[i][1]]=rev
    except KeyError:
        print(sum)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
q = int(input())
ans = sum(A)
many =[0]*(10**5 + 1)
for a in A :
    many[a] += 1

for i in range(q) : 
    B,C = (int(a) for a in input().split())
    many[C] += many[B]
    ans += many[B] * (C-B)
    many[B] = 0
    print(ans)

Submission status: Accepted

Solution code:
N = int(input()) 
A = list(int(i) for i in input().split())  
Q = int(input()) 
B_C = [[int(i) for i in input().split()] for i in range(Q)] 
first_sum = sum(A)
import collections
c = collections.Counter(A)
for i in range(Q):
  change_value = (B_C[i][1]-B_C[i][0])*c[B_C[i][0]]
  c[B_C[i][1]] += c[B_C[i][0]]
  c[B_C[i][0]] = 0
  first_sum += change_value
  print(first_sum)
  #print(c)

Submission status: Accepted

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

Ans = [0] * (10**5 + 1)

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

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

ans = sum(A)
for b, c in BC:
    x = Ans[b]
    Ans[b] = 0
    Ans[c] += x
    ans += (c-b) * x
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=[0]*(10**5)
A=list(map(int,input().split()))
su=0
for i in range(n):
  su+=A[i]
  a[A[i]-1]+=1
q=int(input())
sus=[su]
for i in range(q):
  
  b,c=map(lambda x:int(x)-1,input().split())
  sus.append(sus[-1]+(c-b)*a[b])
  a[c]+=a[b]
  a[b]-=a[b]
  print(sus[-1])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
cnt = Counter(map(int, input().split()))
Asum = sum(k*v for k, v in cnt.items())
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    Asum += (c-b)*cnt[b]
    print(Asum)
    cnt[b], cnt[c] = 0, cnt[b]+cnt[c]

Submission status: Accepted

Solution code:
from collections import Counter

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

ca = [0 for _ in range(10 ** 5 + 1)]

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

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

    sum_a += (c-b) * ca[b]
    print(sum_a)

    ca[c] += ca[b]
    ca[b] = 0

Submission status: Accepted

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

q = int(input())
int_list = [list(map(int, input().split())) for _ in range(q)]
total = 0

# 数字の個数を保存しておくリスト
number = [0] * 100005
for e in a:
    number[e] += 1
    total += e

for i in range(q):

    total -= int_list[i][0] * number[int_list[i][0]]
    total -= int_list[i][1] * number[int_list[i][1]]



    number[int_list[i][1]] += number[int_list[i][0]]
    number[int_list[i][0]] = 0

    total += int_list[i][0] * number[int_list[i][0]]
    total += int_list[i][1] * number[int_list[i][1]]

    print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gcd
from operator import mul
from functools import reduce
from operator import mul
import pprint



sys.setrecursionlimit(2147483647)
INF = 10 ** 20
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)]
mod = 1000000007


n = I()
A = LI()
q = I()
ans = sum(A)
cnt = Counter(A)
for _ in range(q):
    b, c = LI()
    ans += cnt[b] * (c - b)
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int,input().split()))
cnt = Counter(A)
tot = sum(A)
q = int(input())
ans = []
for _ in range(q):
    b,c = map(int,input().split())
    if b not in cnt.keys():
        ans.append(tot)
    else:
        d = cnt[b] * (c-b)
        tot += d
        ans.append(tot)
        cnt[c] += cnt[b]
        cnt[b] = 0
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import collections

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

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

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

Submission status: Accepted

Solution code:
import collections
n = int(input())
list_in = list(map(int, input().split()))
q = int(input())

counter = collections.Counter(list_in)
sum = sum(list_in)

for i in range(q):
    bc = list(map(int, input().split()))
#    list_in = [bc[1] if list_in[l] == bc[0] else list_in[l] for l in range(n)]
    sum_diff = (bc[1] - bc[0]) * counter[bc[0]]
    counter[bc[1]] = counter[bc[1]] + counter[bc[0]]
    counter[bc[0]] = 0
    print(sum+sum_diff)
    sum = sum + sum_diff

Submission status: Accepted

Solution code:

from collections import defaultdict

def main():
  n = int(input())
  d = defaultdict(int)

  for num in map(int, input().split()):
    d[num] += 1

  q = int(input())

  total = sum([k * v for k, v in d.items()])

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



main()

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 = list(map(int, input().split()))
    B.append(b)
    C.append(c)

ans = sum(A)

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

for b, c in zip(B,C):
    d.setdefault(b, 0)
    d.setdefault(c, 0)
    ans -= d[c] * c
    ans -= d[b] * b
    d[c] += d[b]
    d[b] = 0
    ans += d[c] * c
    ans += d[b] * b
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=sum(a)
nums=[0]*(10**5)
for q in a:
  nums[q-1]+=1
# N(10**5)
  
q=int(input())
bc=[]
# N(10**5)
for _ in range(q):
  b,c=map(int,input().split())
  b-=1
  c-=1
  bc.append((b,c))
  
# N(10**5)
for b,c in bc:
  ans-=(b+1)*nums[b]
  ans+=(c+1)*nums[b]
  print(ans)
  nums[c]+=nums[b]
  nums[b]=0

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
MX = 100005
cnt = [0]*MX
for i in a:
    cnt[i] += 1
tot = 0
for i in range(1, MX):
    tot += cnt[i] * i
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    tot += (c - b) * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(tot)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
ans=sum(A)
check=[0]*(10**5+1)
for key in A:
  check[key]+=1
Q=int(input())
for i in range(Q):
  B,C=map(int,input().split())
  if check[B]==0:
    print(ans)
  else:
    x=C-B
    ans+=check[B]*x
    print(ans)
    check[C]+=check[B]
    check[B]=0

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()
N = int(input().rstrip())
*A, = map(int, input().rstrip().split())
ans = sum(A)
dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1
Q = int(input().rstrip())
for _ in range(Q):
    B, C = map(int, input().rstrip().split())
    if B not in dic:
        dic[B] = 0
    if C not in dic:
        dic[C] = 0
    ans += (C-B) * dic[B]
    dic[C] += dic[B]
    dic[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
a_count=Counter(a)
sum=sum(a)
for i in range(q):
  b,c=map(int,input().split())
  if b in a_count:
    sum+=(c-b)*a_count[b]
    a_count[c]+=a_count[b]
    a_count.pop(b)
  print(sum)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

nums = tuple(map(int, input().split()))

count = Counter(nums)
s = sum(nums)

answers = []
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    s = s + (c - b) * count[b]
    count[c] += count[b]
    count[b] = 0
    answers.append(s)
    
for answer in answers:
    print(answer)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
asum = sum(a)
cnt = [0] * (10**5+1)
q = int(input())

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import defaultdict

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

dic = defaultdict(int)
for num in A:
    dic[num] += 1

Q = int(input())

sum_A = sum(A)
for i in range(Q):
    b, c = map(int, input().split())
    sum_A = sum_A - b * dic[b] + c * dic[b] 
    print(sum_A)
    dic[c] += dic.pop(b)

Submission status: Accepted

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

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

s = sum(a)

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = tuple(map(int, input().split()))
S = sum(A)
ct = Counter(A)

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

Submission status: Accepted

Solution code:
from collections import Counter as cnt
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = sum(A)
D = cnt(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
 
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(int)
for a in A:
  d[a]+=1

q = int(input())
sum_a=sum(A)
for _ in range(q):
  b,c=list(map(int,input().split()))
  sum_a+=(c-b)*d[b]#初期配列で数えた数
  d[c]+=d[b]#変換した数を引き継ぎ
  d[b]=0#変換されたので消す
#  print(d)
  print(sum_a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
C = {}
s = 0
for a in map(int, input().split()):
    if a not in C: C[a] = 0
    C[a] += 1
    s += a
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    if b in C:
        if c not in C: C[c] = 0
        s += (c - b) * C[b]
        C[c] += C[b]
        C[b] = 0
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
C = {}
s = 0
for a in map(int, input().split()):
    if a not in C: C[a] = 0
    C[a] += 1
    s += a
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    if b not in C: C[b] = 0
    if c not in C: C[c] = 0
    s += (c - b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(s)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
s,*l=[0]*100002
for i in a[:n]: s+=i; l[i]+=1
for b,c in zip(*[iter(a[n+1:])]*2): s+=(c-b)*l[b]; l[c]+=l[b]; l[b]=0; print(s)

Submission status: Accepted

Solution code:
n,*L=map(int,open(0).read().split())
A,q,Q=L[:n],L[n],L[n+1:]
s,*l=[0]*100002
for i in A: s+=i; l[i]+=1
for b,c in zip(*[iter(Q)]*2): s+=(c-b)*l[b]; l[c]+=l[b]; l[b]=0; print(s)

Submission status: Accepted

Solution code:
import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
Q = int(readline())
sum = sum(A)
d = Counter(A)

for i in range(Q):
    b, c = map(int,readline().split())
    sum += (c-b)*d[b]
    d[c] += d[b]
    d[b] = 0
    print(sum)

Submission status: Accepted

Solution code:
import sys 
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
Q = int(readline())
sum = sum(A)
d = defaultdict(int)

for i in range(N):
    d[A[i]] += 1
       
for i in range(Q):
    b, c = map(int,readline().split())
    sum += (c-b)*d[b]
    d[c] += d[b]
    d[b] = 0
    print(sum)

Submission status: Accepted

Solution code:
f=lambda:map(int,input().split())
f()
s,*l=[0]*100002
for i in f(): s+=i; l[i]+=1
q,=f()
for _ in range(q): b,c=f(); s+=(c-b)*l[b]; l[c]+=l[b]; l[b]=0; print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
m = int(input())
t = [0] * (10 ** 5 + 1)
ans = sum(a)
for i in a:
    t[i] += 1
for i in range(m):
               b, c = map(int,input().split())
               #ans = sum([int(i) for i in a])
               ans -= b * t[b]
               ans += c * t[b]
               t[c] += t[b]
               t[b] = 0
               #ans = ans - a.count("b")(int("c")-int("b"))
               print(ans)

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
f()
s,*l=[0]*100002
for i in f(): s+=i; l[i]+=1
q=f()[0]
for _ in range(q): b,c=f(); s+=(c-b)*l[b]; l[c]+=l[b]; l[b]=0; print(s)

Submission status: Accepted

Solution code:
import collections
n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:#あらかじめ各Aiの個数を数えておく
  cnt[val]+=1
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]#CiがBiに変更されたので、Biの数をCiの数に加える
  cnt[b]=0 #Biの数はゼロになる。

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
q = int(input())
d = defaultdict(int)
 
for i in a:
  d[i] += 1
s = sum(a)
 
for i in range(q):
  b, c = map(int, input().split())
  if b < c:
    x = (c-b)*d[b]
    s += x
  else:
    x = (b-c)*d[b]
    s -= x
  d[c] += d[b]
  d[b] = 0
  print (s)

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
f(); l,q=f(),f()[0]
from collections import *
C,s=Counter(l),sum(l)
for _ in range(q): b,c=f(); s+=(c-b)*C[b]; C[c]+=C[b]; C[b]=0; print(s)

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC = [tuple(map(int, input().split())) for _ in range(Q)]
total = sum(A)

A_dict = {}
for a in A:
    if a in A_dict:
        A_dict[a] += 1
    else:
        A_dict[a] = 1

for i in range(Q):
    b = BC[i][0]
    c = BC[i][1]

    if b in A_dict:
        total += (c - b) * A_dict[b]
        print(total)
        
        if c in A_dict:
            A_dict[c] += A_dict[b]
        else:
            A_dict[c] = A_dict[b]
        A_dict[b] = 0
    
    else:
        print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
q = int(input())
d = defaultdict(int)

for i in a:
  d[i] += 1
s = sum(a)

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

Submission status: Accepted

Solution code:
f=lambda:[*map(int,input().split())]
n,l,q=f()[0],f(),f()[0]
from collections import *
C,s=Counter(l),sum(l)
for _ in range(q): b,c=f(); s+=(c-b)*C[b]; C[c]+=C[b]; C[b]=0; print(s)