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 numpy as np
from collections import Counter

n = map(int,input().split())
a = list(map(int,input().split()))
Q = int(input())
a_count = dict(Counter(a))



def change_dict_key(d, old_key, new_key, default_value=None):
    d[new_key] = d.pop(old_key, default_value)


#change_dict_key(a_count, 1, 5)

#print(a_count)



for q in range(Q):
    num = list(map(int,input().split()))
    
    if(num[0] not in a_count):
        print(np.dot( np.array(list(a_count.keys())) , np.array(list(a_count.values()) ) ) )
        continue

    if(num[1] not in a_count):
        change_dict_key(a_count,num[0],num[1])

    else :
        a_count[num[1]] += a_count[num[0]] 
        del a_count[num[0]] 
    
    #print(a_count.values())

    print(np.dot( np.array(list(a_count.keys())) , np.array(list(a_count.values()) ) ) )
    #print((sum(list_a))  )
"""
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] = list(map(int, input().split()))

bucket = [0]*100001
for i in A:
    bucket[i] += 1

sum = sum(A)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

log=[0]*10**5

for a in A:
    log[a-1]+=1


wa=sum([(i+1)*log[i] for i in range(len(log))])

for _ in range(int(input())):
    B,C=map(int,input().split())
    wa+=(C-B)*log[B-1]
    log[B-1],log[C-1]=0,log[B-1]+log[C-1]
    print(wa)

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

s=sum(a)

#このコードはO(10**10)になる可能性があり、重すぎる
"""
for i in range(q):
  while b[i] in a:
    s+=c[i]-b[i]
    a.remove(b[i])
    a.append(c[i])
  print(s)
"""

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

for i in range(q):
  s+=(c[i]-b[i])*cnt_list[b[i]]
  cnt_list[c[i]]+=cnt_list[b[i]]
  cnt_list[b[i]]=0
  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 _ in range(Q)]

num = [0] * 100001
for a in A:
    num[a] += 1
S = sum(A)
for i in range(Q):
    S += (BC[i][1] - BC[i][0]) * num[BC[i][0]]
    print(S)
    num[BC[i][1]] += num[BC[i][0]]
    num[BC[i][0]] = 0

Submission status: Accepted

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

S = 0
num = [0] * 100001
for a in A:
    S += a
    num[a] += 1
for i in range(Q):
    S += (BC[i][1] - BC[i][0]) * num[BC[i][0]]
    print(S)
    num[BC[i][1]] += num[BC[i][0]]
    num[BC[i][0]] = 0

Submission status: Accepted

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

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

for i in range(q):
    S+=L[Q[i][0]]*(Q[i][1]-Q[i][0])
    L[Q[i][1]]+=L[Q[i][0]]
    L[Q[i][0]]=0
    # print(L)
    print(S)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import Counter
def main():
    n = int(input())
    a = tuple(map(int, input().split()))
    suma = sum(a)
    aa = Counter(a)
    q = int(input())
    m = map(int, read().split())
    for b, c in zip(m, m):
        kosu = aa[b]
        sa = c - b
        suma += sa * kosu
        print(suma)
        aa[b] = 0
        aa[c] += kosu

if __name__ == '__main__':
    main()

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

counter = Counter(A)
counter_sum = sum(k*v for k, v in counter.items())

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

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
M=collections.Counter(A)
ans=0
for j in M.items():
  ans+=j[0]*j[1]
for i in range(Q):
  B,C=map(int,input().split())
  ans+=(C-B)*M[B]
  M[C]+=M[B]
  M[B]=0
  print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
import collections
l=collections.Counter(a)
q=int(input())
s=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    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()))
Q = int(input())
BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]
sum=0
D=[0]*(10**5+1)
for i in range(N):
    sum+=A[i]
    D[A[i]]+=1
for i in range(Q):
    D[C[i]]+=D[B[i]]
    sum+=D[B[i]]*(C[i]-B[i])
    D[B[i]]=0
    print(sum)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
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)]
sum=0
D=[0]*(10**5+1)
for i in range(N):
    sum+=A[i]
    D[A[i]]+=1
for i in range(Q):
    D[C[i]]+=D[B[i]]
    sum+=D[B[i]]*(C[i]-B[i])
    D[B[i]]=0
    print(sum)

Submission status: Accepted

Solution code:
import numpy as np

from collections import defaultdict
N = int(input())
A = tuple(map(int, input().split()))
Q = int(input())
BC= [list(map(int,input().split())) for _ in range(Q)]

counter = defaultdict(int)
for x in A:
    counter[x] += 1

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

Submission status: Accepted

Solution code:
import sys
N = int(input())
A = tuple(map(int, input().split()))
count = [0] * (10 ** 5 + 1)

for a in A:
    count[a] += 1
s = sum(A)

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

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
counter = collections.Counter(A)
total = 0
for k, v in counter.items():
    total += k * v
for i in range(Q):
    B, C = map(int, input().split())
    if counter.get(B) != None:
        count = counter.pop(B)
        counter[C] = counter.get(C, 0) + count
        total -= count * B
        total += count * C
    print(total)

Submission status: Accepted

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

q = int(input())

m = {}

for i in range(1000000):
  m[i] = 0

for e in a:
  m[e] += 1
  
ans = sum(a)

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

def solve():
    """しゃくとり法で解く"""
    N = int(input())
    As = list(map(int, input().split()))

    # 数列Aの要素aが何個あるかを保持する辞書dic
    dic = {}
    for a in As:
        if not a in dic:
            dic[a] = 0
        dic[a] += 1

    S = sum(As)  # 総和

    # 各クエリでしゃくとりする
    Q = int(input())
    for q in range(Q):
        b, c = list(map(int, input().split()))
        if b in dic:
            if not c in dic:
                dic[c] = 0
            S -= b*dic[b]
            S += c*dic[b]
            dic[c] += dic[b]
            dic[b] = 0
        print(S)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  c = Counter(A)
  Q = int(input())
  ans = [0]*Q
  total = sum(A)
  for i in range(Q):
    x,y = map(int, input().split())
    total += c[x]*(y-x)
    c[y] += c[x]
    c[x] = 0
    ans[i] = total
  return ans
print(*solve(),sep='\n')

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())
N=[0]*(10**5)
s=0
for i in range(n):
    N[a[i]-1]+=1
    s+=a[i]
for i in range(q):
    s+=(c[i]-b[i])*N[b[i]-1]
    N[c[i]-1]+=N[b[i]-1]
    N[b[i]-1]=0
    print(s)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = LIST()
q = INT()
count = [0]*(10**5+1)
for x in a:
    count[x] += 1
ans = 0
for i in range(10**5+1):
    ans += i * count[i]
for i in range(q):
    b, c = MAP()
    ans += (c - b) * count[b]
    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())

t = [0] * 110000

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

a = sum(A)

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

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

Submission status: Accepted

Solution code:
import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools
from collections import Counter

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

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as ddict

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

ct=ddict(int)
tt=0
for x in A:
    ct[x]+=1
    tt+=x

for _ in range(Q):
    q=next(sys.stdin)
    a,b=map(int,q.split())
    ct[b]+=ct[a]
    tt+=ct[a]*b-ct[a]*a
    ct[a]=0
    print(tt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as ddict

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

ct=ddict(int)
tt=0
for x in A:
    ct[x]+=1
    tt+=x

for _ in range(Q):
    q=next(sys.stdin)
    a,b=map(int,q.split())
    ct[b]+=ct[a]
    tt+=ct[a]*b-ct[a]*a
    del ct[a]
    print(tt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc171/tasks/abc171_d


N = int(input())

A_list = list(map(int, input().split()))    #整数列
Q = int(input())                            #操作の回数

B_list = []                                 #値がBである要素を
C_list = []                                 #全てCに置き換える

for i in range(Q):
    B, C = map(int, input().split())
    B_list.append(B)
    C_list.append(C)


curr_sum = 0
elements_num_dict = {}

for A in A_list:
    curr_sum += A

    if A in elements_num_dict:
        elements_num_dict[A] += 1
    else:
        elements_num_dict[A] = 1


for i, (B, C) in enumerate(zip(B_list, C_list)):

    if B in elements_num_dict:
        
        count = elements_num_dict[B]
        diff = C*count - B*count
        curr_sum += diff


        # 辞書配列を修正
        elements_num_dict[B] -= count

        if C in elements_num_dict:
            elements_num_dict[C] += count
        else:
            elements_num_dict[C] = count

    
    print(curr_sum)

Submission status: Accepted

Solution code:
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k()
a = l()
q = k()
count = [0]*100001
ans = []
an=sum(a)
for i in range(n):
    x = a[i]
    count[x-1] += 1
for i in range(q):
    b,c=I()
    an += (c-b)*count[b-1]
    count[c-1]+=count[b-1]
    count[b-1]=0
    ans.append(an)

for i in ans:
    print(i)

Submission status: Accepted

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

from collections import defaultdict

def main():
  n = int(input())
  la = list(map(int, input().strip().split()))
  q = int(input())
  counts = defaultdict(int)
  for a in la:
    counts[a] += 1
  s = sum(la)
  for _ in range(q):
    b, c = map(int, input().strip().split())
    s -= b * counts[b]
    s += c * counts[b]
    print(s)
    
    counts[c] += counts[b]
    counts[b] = 0
    

if __name__=='__main__':
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

#bisect.bisect_left(list,key)はlistのなかでkey未満の数字がいくつあるかを返す
#つまりlist[i] < x となる i の個数
#bisect.bisect_right(list, key)はlistのなかでkey以下の数字がいくつあるかを返す
#つまりlist[i] <= x となる i の個数
#これを応用することで
#len(list) - bisect.bisect_left(list,key)はlistのなかでkey以上の数字がいくつあるかを返す
#len(list) - bisect.bisect_right(list,key)はlistのなかでkeyより大きい数字がいくつあるかを返す
#これらを使うときはあらかじめlistをソートしておくこと！
n = int(input())
li = LI()
d = Counter(li)
q = I()
ans = sum(li)
for i in range(q):
    b,c = MI()
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
input = lambda : stdin.readline().strip()
ri = lambda : int(input())
ril = lambda : list(map(int, input().split()))

from collections import defaultdict

N = ri()
A = ril()
Q = ri()
s = sum(A)

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

ans = []
for i in range(Q):
  B, C = ril()
  s += (C - B) * d[B]
  d[C] += d[B]
  d[B] = 0
  ans.append(str(s))

print('\n'.join(ans))

Submission status: Accepted

Solution code:
s=set()
l = [0] * ( 10 ** 5 + 1 )
sum=0
N = int(input())
A = list(map(int, input().split()))
for i in range(len(A)):
    l[A[i]] += 1
    s.add(A[i])
    sum += A[i]
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    if l[B] > 0:
        s.add(C)
        sum = sum + l[B] * ( C - B )
        l[C] += l[B]
        l[B] = 0
        s.discard(B)
    print(sum)

Submission status: Accepted

Solution code:
def freq(my_list):
    count = {} 
    for i in my_list: 
        count[i] = count.get(i, 0) + 1
    return count

n = int(input())
l = list(map(int, input().split()))
s,f = sum(l), freq(l)
for _ in range(int(input())):
    x, y = map(int, input().split())
    if x in f:
        v = f[x]
        if y in f:
            f[y]+=v
            f.pop(x)
        else:
            f[y]=f.pop(x)
        s += (y-x)*v
    print(s)

Submission status: Accepted

Solution code:
def freq(my_list):
    count = {} 
    for i in my_list: 
        count[i] = count.get(i, 0) + 1
    return count

n = int(input())
l = list(map(int, input().split()))
s,f = sum(l), freq(l)
for _ in range(int(input())):
    x, y = map(int, input().split())
    if x in f.keys():
        v = f[x]
        if y in f.keys():
            f[y]+=v
            f.pop(x)
        else:
            f[y]=f.pop(x)
        s += (y-x)*v
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
aa=list(map(int,input().split()))
a=Counter(aa)
aa=sum(aa)
aaa=[]
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  aa+=(c-b)*a[b]
  if c in a.keys():
    a[c]+=a[b]
  else:
    a[c]=a[b]
  a[b]=0
  aaa.append(str(aa))
print('\n'.join(aaa))

Submission status: Accepted

Solution code:
n=int(input())
li=list(map(int,input().split()))
dic={}
ans=0
for i in range(n):
  val=dic.get(li[i],-1)
  if val==-1:
    dic[li[i]]=1
  else:
    dic[li[i]]=val+1
  ans+=li[i]
q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  val=dic.get(a,-1)
  if val==-1 or val==0:
    print(ans)
  else:
    nb=dic.get(b,-1)
    if nb==-1:
      dic[b]=val
    else:
      dic[b]=val+nb
    ans+=(b-a)*val
    dic[a]=0
    print(ans)

Submission status: Accepted

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

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

bucket = [0]*100001
for i in A:
    bucket[i] += 1

sum = sum(A)

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
s = sum(a)
q = int(input())
l = [0] * 100000
for i in a:
    l[i-1] += 1
for i in range(q):
    x,y = map(int, input().split())
    hoge = l[x-1]
    s -= hoge*x
    s += hoge*y
    l[y-1] += hoge
    l[x-1] = 0
    print(s)

Submission status: Accepted

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

int_list = [0 for _ in range(10**5+1)]
sum = 0
for i in A:
   int_list[i] += 1
   sum += i

for B, C in BC_List:
    sum = sum + (C-B) * int_list[B]
    int_list[C] += int_list[B]
    int_list[B] = 0
    print(sum)

Submission status: Accepted

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

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

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

print(*ans, sep="\n")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

total = sum(list(map(lambda item: item[0]*item[1], mp.items())))

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

Submission status: Accepted

Solution code:
import numpy as np
import collections

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

sum_A = np.sum(A)
c = collections.Counter(A)
  
for item in P:
  if item[0] in c.keys():
    sum_A += ((item[1] - item[0]) * c[item[0]])
    if item[1] in c.keys():
      c[item[1]] += c[item[0]]
    else:
      c[item[1]] = c[item[0]]
    c.pop(item[0])
  print(sum_A)

Submission status: Accepted

Solution code:

from collections import Counter

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

ctr = Counter(A)
ans = sum(A)
for b, c in X:
    n = ctr[b]
    ans += -b * n + c * n
    ctr[b] = 0
    ctr[c] += n
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
S = sum(A)
D = {c:0 for c in range(1, 10**5+1)}
for a in A:
  D[a] += 1
for _ in range(int(input())):
  B, C = map(int, input().split())
  S += (C-B)*D[B]
  D[C] += D[B]
  D[B] = 0
  print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict as d
n=int(input())
a=list(map(int,input().split()))
p=d(int)
l=0
for i in a:
    p[i]+=1
    l+=i
for i in range(int(input())):
    b,c=map(int,input().split())
    l+=p[b]*(c-b)
    p[c]+=p[b]
    p[b]=0
    print(l)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = [int(i) for i in input().split()]
all = sum(A)

Q = int(input())
bc = [[int(i) for i in input().split()] for _ in range(Q)]

nums = {i:0 for i in range(1, 10 ** 5 + 1)}
for a in A:
    nums[a] += 1

for i in range(Q):
    #print(nums)
    b, c = bc[i][0], bc[i][1]
    if b in nums.keys(): all += (c - b) * nums[b]
    print(all)

    nums[c] += nums[b]
    nums[b] = 0

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  A=list(map(int,input().split()))
  s=sum(A)
  Q=int(input())
  d=[0]*(10**5 +1)#各数字の個数
  ans=[]
  for i in A:
    d[i]+=1

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

  print("\n".join(map(str, ans)))
  #BC入力ごとに出力するよりまとめて出力した方が倍くらい早い

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  A=list(map(int,input().split()))
  s=sum(A)
  Q=int(input())
  d=[0]*(10**5 +1)#各数字の個数
  ans=[]
  for i in A:
    d[i]+=1

  for i in range(Q):
    B,C=map(int,input().split())
    s += (C-B)*d[B]
    ans.append(s)
    d[C]+=d[B]
    d[B]=0
    
  print("\n".join(map(str, ans)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
  N=int(input())
  A=list(map(int,input().split()))
  s=sum(A)
  Q=int(input())
  d=[0]*(10**5 +1)#各数字の個数
  for i in A:
    d[i]+=1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
s=sum(A)
Q=int(input())
d=[0]*(10**5 +1)#各数字の個数
for i in A:
  d[i]+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n=int(input())
a=input_array()
q=int(input())
BC=[input_array() for _ in range(q)]
SUM=sum(a)

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

for bc in BC:
	diff= bc[1]-bc[0]
	SUM+=diff*A[bc[0]]
	A[bc[1]]+=A[bc[0]]
	A[bc[0]]-=A[bc[0]]
	print(SUM)

Submission status: Accepted

Solution code:
from collections import defaultdict
def query(result, p, b, c):
    result += (c-b) * p[b]
    p[c] += p[b]
    p[b] = 0
    return result, p
N = int(input())
A = [int(i) for i in input().split()]
p = defaultdict(int)
for i in range(N):
    p[A[i]]+= 1
result = sum(A)
Q = int(input())
for i in range(Q):
    b, c = [int(i) for i in input().split()]
    result, p = query(result, p, b, c)
    print(result)

Submission status: Accepted

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

from collections import Counter
D=Counter()

for l in A:
    D[l]+=1
    
for step in range(Q):
    b,c=map(int,input().split())

    if b not in D:
        print(somme)
        continue

    somme=somme+(c-b)*D[b]

    D[c]=D[c]+D[b]
    del D[b]    
    print(somme)

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 -= b * counter[b]
  sum_res += c * 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())
bc=[list(map(int,input().split())) for i in range(q)]
d=[0 for i in range(pow(10,5)+1)]
s=sum(a)
for i in range(n):
    d[a[i]]+=1
for i in range(q):
    s+=(bc[i][1]-bc[i][0])*d[bc[i][0]]
    print(s)
    d[bc[i][1]]+=d[bc[i][0]]
    d[bc[i][0]]=0

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

S = sum(A)
num_dict = {i:0 for i in range(1,100001)}
for i in range(N):
    num_dict[A[i]] += 1

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

Submission status: Accepted

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

task = [0]*Q
for i in range(Q):
    b, c = list(map(int, input().split()))
    task[i] = (b, c)

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

ans = sum(A)

for pair in task:
    B, C = pair
    if count[B]:
        ans -= B * count[B]
        increment = count[B]
        count[C] += count[B]
        count[B] = 0
        ans += C * increment
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Ad, ans = {}, sum(A)
for a in A:
    Ad[a] = Ad.get(a, 0) + 1

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

Submission status: Accepted

Solution code:
n = int(input())
li_a = list(map(int, input().split()))
dic_a = {}

for a in li_a:
    dic_a[a] = dic_a.get(a, 0) + 1

q = int(input())
li_bc = list()

for i in range(q):
    li_bc.append(tuple(map(int, input().split())))


answer = sum(li_a)
for l in li_bc:
    b = l[0]
    c = l[1]

    diff = (c - b) * dic_a.get(b, 0)
    if b in dic_a.keys():
        dic_a[c] = dic_a.get(c, 0) + dic_a.get(b, 0)
        dic_a[b] = 0
        answer += diff
    else:
        pass
    print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

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

C = Counter(a)
ans = sum(a)

for i in range(q):
    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:
import sys
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))

n = Ii()
a = Li()
sa = sum(a)
af = [0]*(10**5+1)
for i in a: 
  af[i]+=1
q = Ii()
for i in range(q):
  b,c = Mi()
  sa = sa + (c-b)*af[b]
  af[c] += af[b]
  af[b] = 0;
  print(sa)