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:
from collections import Counter

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

counter = Counter(a_list)
sum_res = sum(a_list)

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
l = Counter(a)
q = int(input())
ans = sum(a)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)
# input = sys.stdin.readline    ####
def int1(x): return int(x) - 1
def II(): return int(input())
def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())
def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def MS(): return input().split()
def LS(): return list(input())
def LLS(rows_number): return [LS() for _ in range(rows_number)]
def printlist(lst, k=' '): print(k.join(list(map(str, lst))))
INF = float('inf')
# from math import ceil, floor, log2
# from collections import deque
# from itertools import combinations as comb, combinations_with_replacement as comb_w, accumulate, product, permutations
# from heapq import heapify, heappop, heappush
# import numpy as np
# from numpy import cumsum  # accumulate

def solve():
    N = II()
    A = LI()
    Q = II()
    memo = {}
    sm = 0
    for a in A:
        memo[a] = memo.get(a, 0) + 1
        sm = sm + a
    # print(memo, sm)
    for i in range(Q):
        b, c = MI()
        cnt = memo.get(b, 0)
        if cnt == 0:
            print(sm)
            continue
        sm = sm - b * cnt + c * cnt
        memo[b] = 0
        memo[c] = memo.get(c, 0) + cnt
        print(sm)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def Replacing():
    import sys
    input = sys.stdin.readline

    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    
    total = sum(A) # これを基に各queryに対応(加算、減算)する
    
    l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
    for _ in A: # 各インデックスに各keyを加算
        l[_] += 1
    
    for i in range(q):
        b, c = map(int,input().split())
        total += c * l[b] # totalの調整のみ
        total -= b * l[b] # 同上
        print(total)
        l[c] += l[b] # ここでリストの更新
        l[b] = 0 # 同上

Replacing()

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B_to_C = []
for i in range(Q):
  B_to_C.append([int(x) for x in input().split()])

dict_A = {}
sums = 0

for a in A:
  if a in dict_A:
    dict_A[a] += 1
  else:
    dict_A[a] = 1
    
for k, v in dict_A.items():
  sums += k*v
  
for B, C in B_to_C:
  if B in dict_A:
    count_of_num = dict_A[B]
    if C in dict_A:
      dict_A[C] += dict_A[B]
      del dict_A[B]
    else:
      dict_A[C] = dict_A[B]
      del dict_A[B]
      
    sums = sums - B*count_of_num + C*count_of_num
    print(sums)
    
  else:
    print(sums)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

total = sum(A) # これを基に各queryに対応(加算、減算)する

l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
for _ in A: # 各インデックスに各keyを加算
    l[_] += 1

for i in range(q):
    b, c = map(int,input().split())
    total += c * l[b] # totalの調整のみ
    total -= b * l[b] # 同上
    print(total)
    l[c] += l[b] # ここでリストの更新
    l[b] = 0 # 同上

Submission status: Accepted

Solution code:
def Replacing():

    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    
    total = sum(A) # これを基に各queryに対応(加算、減算)する
    
    l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
    for _ in A: # 各インデックスに各keyを加算
        l[_] += 1
    
    for i in range(q):
        b, c = map(int,input().split())
        total += c * l[b] # totalの調整のみ
        total -= b * l[b] # 同上
        print(total)
        l[c] += l[b] # ここでリストの更新
        l[b] = 0 # 同上

Replacing()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

n=int(input().rstrip())
a=[0]*(10**5+1)
now=0
for i in input().split():
    a[int(i)]+=1
    now+=int(i)
for _ in range(int(input().rstrip())):
    b,c=map(int,input().split())
    now-=b*a[b]
    now+=c*a[b]
    print(now)
    a[b],a[c]=0,a[c]+a[b]

Submission status: Accepted

Solution code:
n = int(input())
a = [int(_) for _ in input().split()]
q = int(input())

cnt = [0] * 100001
for i in a:
    cnt[i] += 1

s = sum(a)

bc = [[0] * 2 for _ in range(q)]

for i in range(q):
    bc[i][0], bc[i][1] = map(int, input().split())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

d = dict()

res = 0
for e in a:
    if e in d:
        d[e] += 1
    else:
        d[e] = 1
    res += e

q = int(input())

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())

l =  [int(i) for i in input().split()]

c = Counter(l)

m = int(input())

ans = sum(l)
for i in range(m):
    x,y = [int(i) for i in input().split()]
    
    ans += (y-x) * c[x]
    print(ans)
    
    c[y] += c[x]
    c[x] = 0

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
b_c = [list(map(int, input().split())) for i in range(Q)]

ans = sum(A)
l = Counter(A)
for i in range(Q):
    ans += l[b_c[i][0]] * (b_c[i][1] - b_c[i][0])
    l[b_c[i][1]] += l[b_c[i][0]]
    l[b_c[i][0]] = 0
    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)]

indexA = {}

for a in A:
  if a not in indexA:
    indexA[a] = 0
  indexA[a] += 1

sumA = sum(A)

for (b,c) in BC:
  if b in indexA:
    sumA += (c-b) * indexA[b]
    if c not in indexA:
      indexA[c] = 0
    indexA[c] += indexA[b]
    indexA[b] = 0
  print(sumA)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = Counter(a)
    q = int(input())
    s = sum(a)
    for _ in range(q):
        b, c = map(int, input().split())
        s -= cnt[b]*b

        s += cnt[b]*c
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(s)

if __name__ == "__main__":
    main()

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())
BC = [tuple(map(int, input().split())) for _ in range(Q)]
dic = defaultdict(int)
for a in A:
    dic[a] += 1
tot = 0
for k,v in dic.items():
    tot += k*v
ans = []
for b,c in BC:
    tmp = dic[b]
    tot -= b*tmp
    tot += c*tmp
    dic[c] += tmp
    dic[b] = 0
    ans.append(tot)
print(*ans, sep="\n")

Submission status: Accepted

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

from collections import Counter

def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    c = Counter(A)
    s = sum(A)
    for i in range(Q):
        s += c[B[i]] * (C[i] - B[i])
        c[C[i]] += c[B[i]]
        c[B[i]] = 0
        print(s)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# from math import sqrt, gcd, ceil, log
# from bisect import bisect
from collections import defaultdict, Counter
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))

# sys.setrecursionlimit(10**6)



def solve():
	ans = ""
	n = int(input()); count = Counter(read())
	s = sum([i * count[i] for i in count])
	for _ in range(int(input())):
		a, b = read(); 
		s += (b-a)* count[a]
		count[b] += count[a]
		count[a] = 0
		ans += str(s)+"\n"
	print(ans)
		

if __name__ == "__main__":
	solve()

Submission status: Accepted

Solution code:
x = [0] * 100_001
value = 0

n = int(input())
for a in map(int, input().split()):
  x[a] += 1
  value += a
q = int(input())
for _ in range(q):
  b, c = map(int, input().split())
  value += (c - b) * x[b]
  x[c] += x[b]
  x[b] = 0
  print(value)

Submission status: Accepted

Solution code:
def resolver(N, A, Q, BC):
    total = sum(A)
    counter = dict()
    ans = []
    for a in A:
        counter[a] = counter.get(a, 0) + 1
    
    for (b, c) in BC:
        c0 = counter.pop(b) if b in counter else 0
        counter[c] = counter.get(c, 0) + c0
        total -= c0 * b
        total += c0 * c
        ans.append(total)
    
    return ans

def test():
    pass

def main():

    #test()

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

    ans = resolver(N, A, Q, BC)

    for a in ans:
        print(a)



if __name__ == '__main__':
    main()

Submission status: Accepted

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

table = {}
s = 0
for i in A:
    s+=i
    if i in table: table[i]+=1
    else:table[i] = 1
        
for i in range(Q):
    B,C = map(int,input().split())
    if B in table:
        s -= table[B]*B
        if C in table: table[C]+=table[B]
        else: table[C] = table[B]
        s += table[B]*C
        table[B] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    ans = sum(A)
    counter = Counter(A)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)

MOD = 10 ** 9 + 7
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    dict = defaultdict(int)
    for a in A:
        dict[a] += 1
    answer = sum(A)
    for _ in range(Q):
        b, c = map(int, input().split())
        B = dict[b]

        answer -= b * B
        answer += c * B

        dict[b] = 0
        dict[c] += B
        print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
num = [0] * (10 ** 5 + 1)

for a in A:
    num[a] += 1
_sum = sum(A)

result = []
q = int(input())
for i in range(q):
    b, c = list(map(int, input().split()))
    _sum += (c - b) * num[b]
    num[c] += num[b]
    num[b] = 0
    result.append(str(_sum))
print('\n'.join(result))

Submission status: Accepted

Solution code:
#D                 more faster method than above               see it ..........
l = lambda : list(map(int,input().strip().split()))
n = int(input())
a = l()
t = [0]*(10**5+1)
s = 0
for i in a:
    s += i
    t[i] += 1
q = int(input())
for _ in range(q):
    b,c = l()
    s += (c-b)*t[b]
    t[c] += t[b]
    t[b] = 0
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
count = Counter(input().split())
ans = 0
for v, c in count.items():
    ans += int(v) * c
for i in range(int(input())):
    b, c = input().split()
    if b in count:
        ans -= count.get(b, 0) * int(b)
        prev = count.get(c, 0)
        count[c] = count[b] + count.get(c, 0)
        count[b] = 0
        ans += (count.get(c, 0) - prev) * int(c)
    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)
sum_res=sum(A)
for i in range(Q):
  b,c=map(int,input().split())
  sum_res-=counter[b]*b
  sum_res+=counter[b]*c
  counter[c]+=counter[b]
  counter[b]=0
  print(sum_res)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [list(map(int,input().split())) for _ in range(Q)]
numList = [0]*(10**5+1)
res=sum(A)
for i in A:
    numList[i] += 1

for i in range(Q):
    dev = B[i][1]-B[i][0]
    res += numList[B[i][0]]*dev
    numList[B[i][1]] +=numList[B[i][0]]
    numList[B[i][0]] = 0
    print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
it = lambda: list(map(int, input().strip().split()))
INF = float('inf')

def solve():

    N = int(input())
    A = it()
    Q = int(input())

    S = 0
    E = defaultdict(int)
    for i, a in enumerate(A):
        E[a] += 1
        S += a

    for _ in range(Q):
        B, C = it()
        if E[B] > 0:
            S += (C - B) * E[B]
            E[C] += E[B]
            E[B] = 0
        print(S)
    

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
t=int(input())
import math
a=list(map(int,input().strip().split()))
q=int(input())
h=[0]*(1000000+1)
sumi=0
for i in range(len(a)):
    h[a[i]]+=1
    sumi+=a[i]
 
for i in range(q):
    b,c=map(int,input().strip().split())
    #print(h)
    sumi+=h[b]*(c-b)
    h[c]+=h[b]
    h[b]=0
    #print(h)
    print(sumi)
        
        
        
    #a=list(map(int,input().strip().split()))

Submission status: Accepted

Solution code:


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
nizi = [0] * (10**5+1)
for i in range(len(A)):
    # print(A[i], A)
    nizi[A[i]] += 1
sumall = sum(A)
for q in range(Q):
    # print(nizi)
    B, C = map(int, input().split())
    sumall += (C-B) * nizi[B]
    nizi[C] += nizi[B]
    nizi[B] = 0
    print(sumall)

Submission status: Accepted

Solution code:
def main():
    n = int(input())

    As = list(map(int, input().split()))
    nums = [0] * (10**5+1)
    ans = 0
    for a in As:
        ans += a
        nums[a] += 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
l=[0]*1000000
ans=sum(A)

for i in A:
  l[i]+=1

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

Submission status: Accepted

Solution code:
n = int(input())
a =list(map(int,input().split()))
s =sum(a)
x = [0]*1000001
for i in a:
    x[i] += 1

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [0]*100010
ans = sum(a)

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

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

Submission status: Accepted

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

for ai in a:
    x[ai] += 1  # xのなかでaiが登場する個数のカウント

for _ in range(q):
    b, c = map(int, input().split())
    ans += (c-b) * x[b]
    x[c] += x[b]  # bをcに入れ替えた個数だけcが増加する
    x[b] = 0
    print(ans)

# for i in range(q):
#     count = 0
#     b, c = map(int, input().split())
#
#     for j in a:
#         if j == b:
#             a[count] = c
#         count += 1
#     a_list = [_ for _ in a]
#     ans.append(a_list)
#
# for answer in ans:
#     print(sum(answer))

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]

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

ans = sum(A)

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

    ans -= B * cnt[B]
    ans += C * cnt[B]

    cnt[C] += cnt[B]
    cnt[B] = 0

    print(ans)

Submission status: Accepted

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

for num in a:
    a_list[num-1] += 1

for i in range(len(a_list)):
    sum_n += (i+1)*a_list[i]

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

for num in ans:
    print(num)

Submission status: Accepted

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

cnt = [0 for _ in range(100001)]
for i in a:
    cnt[i] += 1

ans = sum(a)

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

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    ret = sum(A)
    A = Counter(A)

    dic = {}
    for i,v in A.items():
        dic[i]=v
    Q = int(input())
    for q in range(Q):
        b , c = map(int, input().split())
        x = dic.get(b,0)
        dic[c] = dic.get(c,0)+x
        dic[b] = 0
        ret += c*x-b*x

        print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

num_count = [0]*(10**5+1)
tmp_sum = sum(A)
for i in A:
    num_count[i] += 1

for q in range(int(input())):
    B,C = map(int,input().split())
    gain = C*(num_count[B])
    loss = B*(num_count[B])
    num_count[C] += num_count[B]
    num_count[B] = 0
    tmp_sum = tmp_sum + gain - loss
    print(tmp_sum)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
q=int(input())
from collections import Counter
C=Counter(A)

ans=sum(A)
for i in range(q):
  a,b=map(int,input().split())
  ans+=(b-a) * C[a]
  C[b]+=C[a] ; C[a]=0
  print(ans)

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	cal = collections.Counter(al)
	q = int(input())
	s = sum(al)
	for _ in range(q):
		b, c = tin()
		if b in cal:
			s += (c-b)*cal[b]
			if c in cal:
				cal[c] += cal[b]
			else:
				cal[c] = cal[b]
			cal[b]=0
			
		else:
			pass
		
		print(s)
		
		
		
		
		
		
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

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


array = [0]*(10**5+1)
total = sum(A)

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")


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())
    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())
    # 個数を持つ
    # Biの個数 O(1),C[i]の個数 O(1) 更新 O(1) 総和O(1)

    group = [None]*(10**5+1)
    uf = UnionFind(N)

    # union_find
    # N個の数に対して、i番目の数がどのグループに属するのかを示す
    # group
    # j (< 10**5)に対して、jがつけられているグループの根の番号を示す

    for i, a in enumerate(A):
        # グループにつけられている番号がaであるようなグループはあるか？
        # なければ自信のグループにつけられている番号として保持
        # あればそこに合流
        if group[a] is None:
            group[a] = i
        else:
            uf.union(i, group[a])
            group[a] = uf.find(i)
    # print(A)
    # print(group)
    # print(uf.parents)

    tot = sum(A)
    for i in range(Q):
        if group[B[i]] is None:
            b = 0
        elif group[C[i]] is None:
            b = uf.size(group[B[i]])
            group[C[i]] = uf.find(group[B[i]])
            group[B[i]] = None
        else:
            b = uf.size(group[B[i]])
            uf.union(group[B[i]], group[C[i]])
            group[C[i]] = uf.find(group[B[i]])
            group[B[i]] = None
        tot = tot - B[i]*b + C[i]*b
        print(tot)
        # print(group)
        # print(uf.parents)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
_,a,_,*q=[map(int,t.split())for t in open(0)]
s,*d=[0]*8**6
for i in a:s+=i;d[i]+=1
for b,c in q:s+=(c-b)*d[b];d[c]+=d[b];d[b]=0;print(s)

Submission status: Accepted

Solution code:
n = int(input())
count = {}
s = 0
a = [int(c) for c in input().split()]
for val in a:
	s += val
	if (val not in count): count[val] = 1
	else: count[val] += 1

q = int(input())
for _ in range(q):
	b, c = [int(c) for c in input().split()]
	if (b in count):
		temp = count[b]
		count.pop(b)
		s = s + c*temp - b*temp 
		if (c not in count): count[c] = temp 
		else: count[c] += temp
	print(s)

Submission status: Accepted

Solution code:
#from collections import defaultdict

n = int(input())
cnt =[0]*1000000

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

for i in l:
    cnt[i] += 1
    
sums = sum(l)
    
m = int(input())

for i in range(m):
    a,b = map(int, input().split())
    
    diff = (b-a)*cnt[a]
    sums += diff
    print(sums)
    
    cnt[b] += cnt[a]
    cnt[a] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(raw_input())
A = map(int, raw_input().split())

lookup = defaultdict(int)
for a in A:
  lookup[a] += 1
  
cur_sum = 0
for k in lookup:
  cur_sum += k*lookup[k]
  
Q = int(raw_input())
for q in xrange(Q):
  b, c = map(int, raw_input().split())
  cur_sum -= b*lookup[b]
  cur_sum += c*lookup[b]
  
  lookup[c] += lookup[b]
  lookup[b] = 0
  
  print cur_sum

Submission status: Accepted

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

num = [0] * 100010
for i in A:
    num[i] += 1
s = sum(A)

for i in range(Q):
    p, n = BC[i][0], BC[i][1]
    s += (n - p) * num[p]
    num[n] += num[p]
    num[p] = 0
    print(s)

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)

#print(num)
#print(b)
#print(c)


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

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
number=list(map(int,input().split()))
sum_number=sum(number)
Q=int(input())
number_count=Counter(number)


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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

n = int(readline())
a = list(map(int, readline().split()))
q = int(readline())
m = map(int, read().split())

counter = defaultdict(int)

for x in a:
    counter[x] += 1

total = sum(a)

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

Submission status: Accepted

Solution code:
from collections import Counter

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

kosu = dict(Counter(a))

ans = sum(a)

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

    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
from collections import Counter
n=int(input())
*a,=map(int,input().split())
C=Counter(a)
ans=sum(a)
for _ in range(int(input())):
	b,c=map(int,input().split())
	ans+=C[b]*(c-b)
	C[c]+=C[b]
	C[b]=0
	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)
sum_a = sum(a)

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

  print(sum_a)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int, input().split()))
r = sum(As)
nAs = {}
for A in As:
  if A not in nAs:
    nAs[A] = 0
  nAs[A] += 1
Q = int(input())
for i in range(Q):
  B, C = map(int, input().split())
  if B not in nAs:
    print(r)
    continue
  n = nAs[B]
  if C not in nAs:
    nAs[C] = 0
  r += (C-B)*n
  nAs[B] = 0
  nAs[C] += n
  print(r)

Submission status: Accepted

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

count = np.zeros(10**5+1) 
for i in range(N):
  idx = A[i]
  count[idx] += 1

total = sum(A)
for i in range(Q):
  B, C = map(int, input().split())
  count_B = count[B]	# Bの個数
  count[B] = 0
  count[C] += count_B	# 数値を置き換えた時の、その数値の数
  total = total - int(count_B*B) + int(count_B*C)
  print(total)

Submission status: Accepted

Solution code:
p105=100009
count = [0]*p105
n = int(input())
a = list(map(int,input().split()))
sum=0
for i in range(n):
    count[a[i]]+=1
    sum+=a[i]

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

    print(sum)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())

A = [int(x) for x in input().split(" ")]
Q = int(input())
d = defaultdict(int)

ans_sum = 0
for a in A:
    d[a] += 1
    ans_sum += a

for q in range(Q):
    B, C = map(int, input().split())
    num = d[B]
    ans_sum -= num * B
    ans_sum += num * C
    d[B] = 0
    d[C] += num
    print(ans_sum)

Submission status: Accepted

Solution code:
from collections import *

N = int(input())
A = list(map(int, input().split()))
ans = sum(A)
cnt = Counter(A)

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