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
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
cnt=Counter(a)
ans=sum(a)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    ans+=(c-b)*cnt[b]
    ##print(cnt)#Counter({1: 1, 2: 1, 3: 1, 4: 1})
    cnt[c]+=cnt[b]
    ##print(cnt)#Counter({2: 2, 1: 1, 3: 1, 4: 1})
    cnt[b]=0
    ##print(cnt)#Counter({2: 2, 3: 1, 4: 1, 1: 0})
    print(ans)

Submission status: Accepted

Solution code:
import array

N = int(input())
A = array.array('L', list(map(int, input().split())))
MAX = 10**5+1
X = array.array('L', [0]) * MAX
Y = array.array('L', range(MAX))

for i in range(len(A)): X[A[i]] += 1
    
Q = int(input())
cur = sum(array.array('L', (X[i]*Y[i] for i in range(len(X)))))

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

Submission status: Accepted

Solution code:
def main():
	N = int(input())
	A = [int(a) for a in input().split(" ")]
	S = sum(A)
	cA = [0] * 1000001
	for i in range(len(A)):
		cA[A[i]] += 1
	Q = int(input())
	for i in range(Q):
		B, C = [int(x) for x in input().split(" ")]
		diff = (C-B)*cA[B]
		S += diff
		cA[C] += cA[B]
		cA[B] = 0
		print(S)

main()

Submission status: Accepted

Solution code:
n = int(input())
a_list = [int(i) for i in input().split()]
a_dict = {}
for a in a_list:
  if a in a_dict:
    a_dict[a] += 1
  else:
    a_dict[a] = 1
q = int(input())
si = 0
for a in a_dict:
  si += a * a_dict[a]
for _ in range(q):
  bi, ci = [int(i) for i in input().split()]
  if not bi in a_dict:
    print(si)
    continue
  if not ci in a_dict:
    a_dict[ci] = 0
  a_dict[ci] += a_dict[bi]
  si += (ci - bi) * a_dict[bi]
  a_dict[bi] = 0
  print(si)

Submission status: Accepted

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

X=[0]*(10**5+1)
for i in range(N):
  X[A[i]]+=1
  S=S+A[i]

#print(A)
#print(B)
#print(C)

for i in range(Q):
  X[C[i]]+=X[B[i]]
  S=S+X[B[i]]*(C[i]-B[i])
  X[B[i]]=0
  print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
C_A = Counter(A)
S = 0
for ca in C_A:
  S += ca * C_A[ca]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import*
_,A,_,*Q=[map(int,l.split())for l in open(0)];s=sum(A:=[a for a in A]);C=Counter(A)
for b,c in Q:s+=(c-b)*C[b];C[c]+=C[b];C[b]=0;print(s)

Submission status: Accepted

Solution code:
from collections import*
_,A,_,*Q=[map(int,l.split())for l in open(0)];A=[a for a in A];s=sum(A);C=Counter(A)
for b,c in Q:s+=(c-b)*C[b];C[c]+=C[b];C[b]=0;print(s)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

asum = sum(a)
adic = {}

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


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

Submission status: Accepted

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

dict_a = {}
current_sum = 0
for i in range(n):
  dict_a[a[i]] = dict_a.get(a[i],0)+1
  current_sum += a[i]

for i in range(q):
  b,c = map(int,input().split())
  diff = c-b
  
  rep_num = dict_a.get(b,0)
  current_sum += diff*rep_num
  print(current_sum)
  
  dict_a[b] = 0
  dict_a[c] = dict_a.get(c,0) + rep_num

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
sums = sum(a)
d = {}

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

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

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
d = dict()
for i in arr:
	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):
		s -= b * d[b]
		s += c * d[b]
		if (c not in d):
			d[c] = d[b]
		else:
			d[c] += d[b]
		d.pop(b)
	print(s)

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

asum=sum(a) #当初の数列Aの要素の和
d={}

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

for b,c in bc:
  if b in d:
    asum+=d[b]*(c-b)
    if c in d:
      d[c]+=d[b]
    else:
      d[c]=d[b]
    d[b]=0
  print(asum)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
li = [int(x) for x in input().split()]
Q = int(input())

d = defaultdict(int)

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

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

Submission status: Accepted

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

from collections import Counter


def solve(N: int, A: "List[int]", Q: int, BC: "List[(int,int)]"):
    A = Counter(A)
    answers = []
    ans = ans = sum((i * n for i, n in A.items()))
    for b, c in BC:
        if b != c:
            ans += (c - b) * A[b]
            A[c] += A[b]
            del A[b]
        answers.append(ans)
    return answers


def main():
    N = int(input())  # type: int
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [tuple(map(int, input().split())) for _ in range(Q)]
    answer = solve(N, A, Q, BC)
    for ans in answer:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n = I()
    suuretu = LI()
    q = I()
    dic = collections.Counter(suuretu)
    nowsum = sum(suuretu)
    
    for _ in range(q):
        b,c = LI()
        cnt = dic[b]
        nowsum += (c-b)*cnt
        print(nowsum)
        dic[b] = 0
        dic[c] += cnt
main()

Submission status: Accepted

Solution code:
n=int(input())
arr=[int(i) for i in input().strip().split(" ")]
t=int(input())
dic={}
sum_array=0
for i in arr:
    dic[i]=dic.get(i,0)+1
    sum_array+=i
    

for _ in range(t):
    a,b=[int(i) for i in input().split(" ")]
    if a not in dic:
        print(sum_array)
        continue
    if b in dic:
        dic[b]+=dic[a]
    else:
        dic[b]=dic[a]
    
    sum_array+=dic[a]*(b-a)
    print(sum_array)
    dic[a]=0

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import collections
N = int(input())
s = input().split()
b = [str(l) for l in s]
c = collections.Counter(b)

K = int(input())
t = [input().split() for i in range(K)]

d = int(0)
e = int(0)
ans = int(0)
ckey = []
cvalue = []
clen = int(len(c))

for i in c.keys():
    ckey.append(i)
for i in c.values():
    cvalue.append(i)
for i in range(clen):
    ans = ans + int(ckey[i]) * int(cvalue[i])
    
for i in range(K):
    if c.get(t[i][0]) != None:
        d = c.get(t[i][0])
        if c.get(t[i][1]) != None:
            e = c.get(t[i][1])
            ans = ans - int(t[i][0]) * int(d) + int(t[i][1]) * int(d)
            print(ans)
            c[t[i][1]] = int(d) + int(e)
            c[t[i][0]] = 0
        else:
            ans = ans - int(t[i][0]) * int(d) + int(t[i][1]) * int(d)
            print(ans)
            c[t[i][1]] = int(d)
            c[t[i][0]] = 0
    else:
        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)
s = sum(a)

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

Submission status: Accepted

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

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

for x in A:
    X[x] += 1

Q = int(input())

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

Submission status: Accepted

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

# Aの値について数列を作る
# A_num = [A.count(i) for i in range(10 ** 5 + 1)]

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

Si = sum(A)

for BC in BCs:
    # BC[0] ...　置換前の値
    # BC[1] ...　置換後の値
    
    if A_num[BC[0]] > 0: 
        Si += A_num[BC[0]] * (BC[1] -BC[0])
        A_num[BC[1]] += A_num[BC[0]]
        A_num[BC[0]] = 0

    print(Si)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
d = {}
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
for b, c in BC:
    if b in d:
        total += d[b] * (c-b)
        if c in d:
            d[c] += d[b]
        else:
            d[c] = d[b]
        d[b] = 0
    print(total)

Submission status: Accepted

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

Q = int(input())

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

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

B = []
C = []
for i in range(Q):
    Bi, Ci = list(map(int, input().split()))
    B.append(Bi)
    C.append(Ci)

for i in range(Q):
    Bi = B[i]
    Ci = C[i]
    ans += Ci*counter[Bi] - Bi*counter[Bi]
    print(ans)
    counter[Ci] += counter[Bi]
    counter[Bi] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict

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

sm = 0
cnt = defaultdict(int)
for i in a:
    sm += i
    cnt[i] += 1

for _ in range(q):
    b, c = list(map(int, input().split()))
    if b in cnt:
        sm -= cnt[b] * b
        sm += cnt[b] * c

        cnt[c] += cnt[b]
        del cnt[b]
    print(sm)

Submission status: Accepted

Solution code:
def abc171d_replacing():
    n = int(input())
    a = list(map(int, input().split()))
    a_dict = {}
    for v in a:
        if a_dict.get(v) is None:
            a_dict[v] = 1
        else:
            a_dict[v] += 1
    q = int(input())
    s = []
    total = 0
    for k, v in a_dict.items():
        total += k * v
    for _ in range(q):
        b, c = map(int, input().split())
        if b in a_dict.keys():
            total += (c * a_dict[b] - b * a_dict[b])
            if c in a_dict.keys():
                a_dict[c] += a_dict[b]
            else:
                a_dict[c] = a_dict[b]
            del a_dict[b]
        s.append(total)

    for v in s:
        print(v)


abc171d_replacing()

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)



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

tot = sum(A)
cnt = [0] * 100001
for i in A:
    cnt[i] += 1

# print(cnt[:6])

for l in B_C:
    cnt[l[1]] += cnt[l[0]]
    tot += cnt[l[0]] * (l[1] - l[0])
    cnt[l[0]] = 0
    print(tot)

Submission status: Accepted

Solution code:
from collections import Counter
#N, K = map(int, input().split( ))
#L = list(map(int, input().split( )))
N = int(input())
A = list(map(int, input().split( )))
Q = int(input())
Sum = sum(A)
#Counterなるものがあるらしい
coun = Counter(A)
#Q個の整数の組(B,C)が与えられてB \to Cとして合計を計算
#合計は(Ci-Bi)*(A.count(Bi))変化する.
for _ in range(Q):
  b, c = map(int, input().split( ))
  Sum += (c-b)*coun[b]
  coun[c] += coun[b]
  coun[b] = 0
  print(Sum)
  # replaceするとタイムエラーになるのか…
  #  A = [c if a == b else a for a in A]

Submission status: Accepted

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

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

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

xxx=sum(a)

q=int(input())

for i in range(q):
  l,r=map(int,input().split())
  pin=cnt[l]
  cnt[r]+=pin
  cnt[l]=0

  xxx+=(r-l)*pin

  print(xxx)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    import sys

    input = sys.stdin.readline

    _ = int(input())
    lst = [0 for _ in [0] * (10 ** 5 + 1)]
    sum_lst = 0
    for a in [int(x) for x in input().split()]:
        sum_lst += a
        lst[a] += 1
    Q = int(input())

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

        sum_lst += (C - B) * lst[B]
        print(sum_lst)
        lst[C] += lst[B]
        lst[B] = 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    A = [int(i) for i in input().split()]
    counter = {}
    total = 0
    for num in A:
        total += num
        counter[num] = counter.get(num, 0) + 1

    Q = int(input())
    for i in range(Q):
        B,C = [int(i) for i in input().split()]
        if B in counter:
            B_cnt = counter[B]
            counter[C] = counter.get(C, 0) + B_cnt
            total += (C-B) * B_cnt
            counter[B] = 0
        print(total)

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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


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

main()

Submission status: Accepted

Solution code:
sum = 0
num = [0] * (10 ** 5 + 1)
N = int(input())
A = [int(a) for a in input().split()]
for i in range(0, N):
    sum += A[i]
    num[A[i]] += 1

Q = int(input())
for i in range(0, Q):
    B, C = (int(x) for x in 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())
sm = sum(a)
hm = [0] * (10 ** 5 + 1)
for i in a:
    hm[i] += 1
for _ in range(q):
    b, c = map(int, input().split())
    sm += (c - b) * hm[b]
    hm[c] += hm[b]
    hm[b] = 0
    print(sm)

Submission status: Accepted

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


def next_line():
    return input()


def next_int():
    return int(input())


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


def next_int_array_multi_lines(size):
    return [int(input()) for _ in range(size)]


def next_str_array(size):
    return [input() for _ in range(size)]


def main():
    n = next_int()
    ar = next_int_array_one_line()
    num = [0] * 100001
    for a in ar:
        num[a] += 1
    q = next_int()
    res = 0
    for i in range(len(num)):
        res += num[i] * i

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


if __name__ == '__main__':
    main()

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())
    
import collections
c = collections.Counter(A)
startsum = sum(A)
for i in range(Q):
    Bcount = c[B[i]]
    c[B[i]] = 0
    Ccount = c[C[i]]
    c[C[i]] += Bcount
    startsum += (C[i]-B[i])*Bcount
    print(startsum)

Submission status: Accepted

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

Submission status: Accepted

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

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

q=int(input())

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

Submission status: Accepted

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

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

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 = [0]*100001
for i in A:
    num[i] += 1

S = [0]*(Q+1)
S[0] = sum(A)
change = 0
for i in range(Q):
    change = num[B[i]]
    S[i+1] = S[i] + change*(C[i]-B[i])
    num[B[i]] -= change
    num[C[i]] += change
    
for i in S[1:]:
    print(i)

Submission status: Accepted

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


s=sum(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Q=int(input())
for q in range(Q):
  b,c = map(int,input().split())
  ans += c*count[b] - b*count[b]
  count[c] += count[b]
  count[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())
sum_res = sum(A)
counter = Counter(A)

for _ in range(Q):
    B, C = map(int, input().split())
    sum_res += (C - B) * counter[B]
    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())
sum_res = sum(A)
counter = [0 for _ in range(10 ** 5 + 1)]

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

for _ in range(Q):
    B, C = map(int, input().split())
    sum_res += (C - B) * counter[B]
    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())
sum_res = sum(A)
counter = [0 for _ in range(10 ** 5 + 1)]

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

table = defaultdict(int)
ans = 0
for a in A:
    table[a] += 1
    ans += a

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline
    input()
    a = tuple(map(int, input().split()))
    ans = sum(a)
    a = Counter(a)
    for _ in range(int(input())):
        b, c = map(int, input().split())
        if b in a:
            ans += (c - b) * a[b]
            a[c] = a[c] + a[b] if c in a else a[b]
            del a[b]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline
    input()
    a = list(map(int, input().split()))
    ans = sum(a)
    a = Counter(a)
    for _ in range(int(input())):
        b, c = map(int, input().split())
        if b in a:
            ans += (c - b) * a[b]
            print(ans)
            if c in a:
                a[c] += a[b]
            else:
                a[c] = a[b]
            del a[b]
        else:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline
    input()
    a = Counter(map(int, input().split()))
    ans = sum(k * v for k, v in a.items())
    for _ in range(int(input())):
        b, c = map(int, input().split())
        if b in a:
            ans += (c - b) * a[b]
            print(ans)
            a[c] = a[c] + a[b] if c in a else a[b]
            del a[b]
        else:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline
    input()
    a = list(map(int, input().split()))
    ans = sum(a)
    a = Counter(a)
    for _ in range(int(input())):
        b, c = map(int, input().split())
        if b in a:
            ans += (c - b) * a[b]
            print(ans)
            a[c] = a[c] + a[b] if c in a else a[b]
            del a[b]
        else:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter

    input = sys.stdin.readline
    input()
    a = tuple(map(int, input().split()))
    ans = sum(a)
    a = Counter(a)
    for _ in range(int(input())):
        b, c = map(int, input().split())
        if b in a:
            ans += (c - b) * a[b]
            print(ans)
            a[c] = a[c] + a[b] if c in a else a[b]
            del a[b]
        else:
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

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

N=int(input())
A=list(map(int,input().split()))
B=[0]*(10**5)
for a in A:
  B[a-1]+=1
s=sum(A)
Q=int(input())
for i in range(Q):
  b,c=map(int,input().split())
  bb,bc=B[b-1],B[c-1]
  B[c-1]+=bb
  B[b-1]=0
  s+=bb*c-bb*b
  print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

Q = int(input())


A_li.sort()
res = sum(A_li)
main_li = {}

now = 0
for i in A_li:
    if i == now:
        main_li[i] += 1
    else:
        main_li[i] = 1
        now = i


# クエリの処理
for _ in range(Q):
    B, C = list(map(int, input().split()))
    if B not in main_li.keys():
        print(res)
        continue
    if C in main_li.keys():
        main_li[C] += main_li[B]
    else:
        main_li[C] = main_li[B]
    res += (C - B) * main_li[B]
    main_li.pop(B)
    print(res)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
S = sum(A)

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

Submission status: Accepted

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

counts = [ 0 for __ in range(10**5+1)]
answer = sum(nums)

for num in nums:
  counts[num] += 1

for b, c in operations:
  answer += counts[b]*(c-b)
  print(answer)
  counts[c] += counts[b]
  counts[b] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
arr = list(input().split())
q = int(input())
num_counts = defaultdict(lambda: 0)
ans = 0

for i in arr:
  num_counts[i] += 1
  ans += int(i)

for _ in range(q):
  bef, af = list(input().split())
  apper_count = num_counts[bef]
  ans += (int(af) - int(bef)) * apper_count
  num_counts[bef] -= apper_count
  num_counts[af] += apper_count
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

asum = sum(A)
S={}
for i in range(len(A)):
    if A[i] in S:
        S[A[i]]+=1
    else:
        S[A[i]]=1

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

    asum+=diff
    D.append(asum)

for d in D:
    print(d)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = list(map(int,input().split()))
    q = int(input())
    c = Counter(a)
    allsum = 0
    for k,v in c.items():
        allsum += k*v
    ans = []
    for i in range(q):
        bi,ci = list(map(int,input().split()))
        allsum += ci*c[bi] - bi*c[bi]
        c[ci] = c[ci] + c[bi]
        c[bi] = 0
        ans.append(allsum)
    for i in ans:
        print(i)    
main()

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(a)

allsum = 0
for k,v in c.items():
    allsum += k*v
    
ans = []

for i in range(q):
    bi,ci = list(map(int,input().split()))
    allsum += ci*c[bi] - bi*c[bi]
    c[ci] = c[ci] + c[bi]
    c[bi] = 0
    ans.append(allsum)
    
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from collections import Counter

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

# bc = [list(map(int,input().split())) for _ in range(q)]

c = Counter(a)

allsum = 0
for k,v in c.items():
    allsum += k*v
    
ans = []

for i in range(q):
    bi,ci = list(map(int,input().split()))
    allsum += ci*c[bi] - bi*c[bi]
    c[ci] = c[ci] + c[bi]
    c[bi] = 0
    ans.append(allsum)
    
for i in ans:
    print(i)