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

def main(args):
    N = int(input())
    A = list(map(int,input().split()))
    
    ans = sum(A)
    count = [0]*(10**5+1)
    
    for a in A:
        count[a] += 1
    
    #print(count[:5])
    
    Q = int(input())
    for i in range(Q):
        B, C = map(int,input().split())
        ans -= B*count[B]
        count[C] += count[B]
        #print(count[:5])
        ans += C*count[B]
        count[B] = 0
        print(ans)
        
if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

ans = sum(A)
dic = {a+1:0 for a in range(10**5)}
for a in A:
  dic[a] += 1

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

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
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)

N = i()
A = l()
Q = i()
c = dict(Counter(A))
ans = sum(A)
for i in range(Q):
    B,C = I()
    if B in c:
        b = c.pop(B)
        ans += b*(C-B)
        d = 0
        if C in c:
             d = c.pop(C)
        c[C] = b+d
    print(ans)

Submission status: Accepted

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

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

LL=[[] for _ in range(Q)]
for i in range(Q):
    out=0
    B,C=map(int,input().split())
    LL[i]=Sout+(C-B)*Val[B]
    Val[C]+=Val[B]
    Val[B]=0
    Sout=LL[i]
for ll in LL:
    print(ll)

Submission status: Accepted

Solution code:
from collections import defaultdict
D=defaultdict(int)
N=int(input())
A=list(map(int,input().split()))

for x in A:
    D[x]+=1
Q=int(input())
ans=0
for value,key in D.items():
    ans+=value*key

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

Submission status: Accepted

Solution code:
from collections import defaultdict

def t():
    return 0

n = int(input())
a = [int(x) for x in input().split()]

counter = defaultdict(t)

for x in a:
    counter[x] += 1
# print(dict(counter))

s = sum(a)

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

Submission status: Accepted

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

# input
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = [-1 for _ in range(q)]
c = [-1 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

def innerproduct(d):
    ans = 0
    for key, value in d.items():
        ans += int(key)*int(value)
    return ans

# calc
d = {}
for i in a:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1

# print(d)
ans = sum(a)
for i in range(q):
    if b[i] in d:
        ans -= b[i]*d[b[i]]
        tmp = d[b[i]]
        if c[i] not in d:
            d[c[i]] = d[b[i]]
        else:
            d[c[i]] += d[b[i]]
        d[b[i]] = 0
        ans += tmp*c[i]

#    print(d)
    print(ans)

Submission status: Accepted

Solution code:
      
NN = 100001

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

number = [0 for _ in range(NN)]
summ = 0
for a in A:
  number[a] += 1
  summ += a 
Q = int(input())

#mapping = [0 for _ in range(NN)]
for i in range(Q):
  B, C = map(int,input().split())
  summ += number[B]*(C-B)
  number[C] += number[B]
  number[B] = 0
  """
  summ += 
  if uf.parents[B] < 0:
    summ += -uf.parents[B] * (C-B)
    uf.union(C, B) 
  """
  print(summ)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n = I()
a = RI()
q = I()
bc = LI(q)

s = sum(a)

d = defaultdict(int)
for i in range(n):
    d[ a[i] ] += 1
# print(d)   

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

Submission status: Accepted

Solution code:
#import numpy as np
from collections import Counter
from time import time

import sys
readline = sys.stdin.buffer.readline


N = int(input())
A = list(map(int, input().split()))
#A = np.random.randint(1, 10 ** 5 + 1, 10 ** 5)

S = sum(A)
C = Counter(A)

Q = int(input())
#Q = 10 ** 5

ans = []
s = time()
for _ in range(Q):
    b, c = map(int, input().split())
    #b, c = np.random.randint(1, 10 ** 5 + 1, 2)
    #b, c = 2, 5

    count = C[b]
    S = S + (c - b) * count

    C[c] += count
    C[b] = 0
    
    ans.append(S)

print('\n'.join(map(str, ans)))
#print('time: ', time() - s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections


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

sum = sum(A)
count = collections.Counter(A)

for x, y in B:
    change = y - x
    if x in count:
        sum += change * count[x]
        if y in count:
            count[y] += count[x]
        else:
            count[y] = count[x]

        del count[x]
    print(sum)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
#b=[0]*q
#c=[0]*q
ans=0
l=[0]*1000001
for i in range(n):
    ans+=a[i]
    l[a[i]]+=1

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

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for _ in range(q)]
dic={}
for i in range(n):
    if a[i] in dic:
        dic[a[i]]+=1
    else:
        dic[a[i]]=1
s=sum(a)
for i in range(q):
    b,c=bc[i]
    if b not in dic:
        print(s)
        continue
    else:
        print(s+(c-b)*dic[b])
        s+=(c-b)*dic[b]
        if c not in dic:
            dic[c]=dic[b]
        else:
            dic[c]+=dic[b]
        dic[b]=0

Submission status: Accepted

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

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

    d = dict()

    # dictに格納 O(1)
    for a in A:
        try:
            d[a] += 1
        except KeyError:
            d[a] = 1
    
    ans = 100000000000000000000000000
    ans = 0

    # 一旦ans出す
    for dat in d.items():
        ans += dat[0]*dat[1]

    # B,Cの操作
    # for bc in BC:
    #     try:
    #         d[bc[1]] += d[bc[0]]
    #     except KeyError:
    #         try:
    #             d[bc[1]] = d[bc[0]]
    #         except KeyError:
    #             d[bc[0]] = 0
    #             d[bc[1]] = 0
    #     finally:
    #     # 増減分だけ変更
    #         ans += bc[1]*d[bc[0]] - bc[0]*d[bc[0]]
    #         d[bc[0]] = 0
    #     print(ans)

    # B,Cの操作
    for bc in BC:
        if bc[0] in d:
            if bc[1] in d:
                d[bc[1]] += d[bc[0]]
                ans += bc[1]*d[bc[0]] - bc[0]*d[bc[0]]
                d[bc[0]] = 0
            else:
                d[bc[1]] = d[bc[0]]
                ans += bc[1]*d[bc[0]] - bc[0]*d[bc[0]]
                d[bc[0]] = 0
        else:
            pass
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
Numbers = {}
A = list(map(int,input().split()))
for i in range(N):
    Av = A.pop()
    if Av not in Numbers:
        Numbers[Av] = 1
    else:
        Numbers[Av] += 1
Ans = 0
for v,i in Numbers.items():
    Ans += v*i
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    if B in Numbers:
        Mo = Numbers[B]
        if C not in Numbers:
            Numbers[C] = Mo
            Numbers[B] = 0
        else:
            Numbers[C] += Mo
            Numbers[B] = 0
        Ans += Mo *C - Mo*B
        print(Ans)
    else:
        print(Ans)

Submission status: Accepted

Solution code:
from collections import Counter
# from fractions import gcd # >=Python3.5 # lcm（最小公倍数） = (a*b)//gcd(a,b)
# from fractions import Fraction
# from math import gcd # <Python3.5
# from math import sqrt

#input = sys.stdin.readline
#def main():

#---------------------------------------------------------

n = int(input())
li = list(map(int,input().split()))
q = int(input())
ope = [list(map(int,input().split())) for i in range(q)]

cnt = Counter(li)

ans = sum(li)

for i in range(q):
    sub = ope[i][1]-ope[i][0]
    ans += cnt[ope[i][0]]*sub
    print(ans)
    cnt[ope[i][1]]+=cnt[ope[i][0]]
    cnt[ope[i][0]]=0

Submission status: Accepted

Solution code:
import collections

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

l = [0] * (10**5 + 1)
# print(l)
# print(len(l))
c = collections.Counter(A)
# print(c)
for key in c:
    l[key] = c[key]
# print(l)
ans = 0
for item in c:
    ans += item * c[item]

# print(ans)  # i=0

for i in range(Q):
    if B[i] in c:
        # print(c)
        ans = ans - B[i] * c[B[i]] + C[i] * c[B[i]]
        c[C[i]] += c[B[i]]
        c.pop(B[i])
    print(ans)

Submission status: Accepted

Solution code:
#sum を計算しておく
n=int(input())
a=[int(i) for i in input().split()]
a.sort()
q=int(input())
bc=[]
for i in range(q):
    bc.append([int(i) for i in input().split()])

import collections
collect = collections.Counter(a)

ans=0
for k,v in collect.items():
    ans += (k * v)
for i in bc:
    if i[0] in collect:
        if i[1] in collect:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] += collect.pop(i[0],0)
        else:
            ans += ((i[1]-i[0]) * collect[i[0]])
            collect[i[1]] = collect.pop(i[0],0)
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
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)]
sa=sum(a)
hako=deque([0 for _ in range(10**5+1)])
aa=Counter(a)
for i in aa:
    hako[i]=aa[i]
# print(hako)

for i in range(q):

    sa+=(bc[i][1]-bc[i][0])*hako[bc[i][0]]
    print(sa)
    hako[bc[i][1]]+=hako[bc[i][0]]
    hako[bc[i][0]]=0
    # print(hako)




# print(hako)

Submission status: Accepted

Solution code:
import math  # noqa: F401
from typing import Dict, List, Optional, Tuple, Union  # noqa: F401


def count(A: List[int]) -> Dict[int, int]:
    D: Dict[int, int] = {}
    for a in A:
        if a not in D:
            D[a] = 1
        else:
            D[a] += 1
    return D


def main(N: int, A: List[int], Q: int, B: List[int], C: List[int]):
    D = count(A)
    sum_ = sum(A)
    for b, c in zip(B, C):
        sum_changing = D.get(b, 0) * (c - b)
        if c not in D:
            D[c] = 0
        D[c] += D.get(b, 0)
        D[b] = 0
        sum_ += sum_changing
        print(sum_)


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B: List[int] = []
    C: List[int] = []
    for _ in range(Q):
        b, c = map(int, input().split())
        B.append(b)
        C.append(c)
    main(N, A, Q, B, C)

Submission status: Accepted

Solution code:
# import sys
# input = sys.stdin.readline
# import re
# import itertools
import collections

def main():
    n = int(input())
    s = input_list()
    sc = collections.Counter(s)
    q = int(input())
    data = []
    for i in range(q):
        b, c = input_list()
        sc[c] += sc[b]
        if i > 0:
            data.append(c*sc[b] - b * sc[b])
        if b in sc:
            sc.pop(b)
    ans = 0
    for k, v in sc.items():
        ans += k*v
    aa = [ans]
    for i, v in enumerate(data[::-1]):
        aa.append(aa[i] - v)
    for a in aa[::-1]:
        print(a)


def count_tento(l, cur):
    count = 0
    for v in l:
        if v > cur:
            count += 1
    return count

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

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    alis = sorted(map(int, input().split()))
    total = sum(alis)
    adic = {}
    for num in alis:
        if num in adic:
            adic[num] += 1
        else:
            adic[num] = 1
    
    anslis = []

    q = int(input())
    bclis = []
    for i in range(q):
        b, c = map(int,input().split())
        if b in adic:
            kazu = adic[b]
            adic[b] = 0
            total -= b * kazu
            if c in adic:
                adic[c] += kazu
            else:
                adic[c] = kazu
            total += c * kazu
        print(total)
    
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
nums = list(map(int, input().split()))
Q = int(input())
nums_hash = collections.Counter(nums)
sum_point = sum(nums)
for _ in range(Q):
    # print(nums_hash)
    b, c = map(int, input().split())
    if b in nums_hash:
        sum_point = (sum_point - (b * nums_hash[b]) + (c * nums_hash[b]))
    print(sum_point)
    nums_hash[c] += nums_hash[b]
    nums_hash[b] = 0

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
temparr = input()
temparr = temparr.split()
dicts = {}
total = 0 
for i in temparr:
    i = int(i)
    if i not in dicts:
        dicts[i] = 1 
    else:
        dicts[i] += 1 
    total += i 
times = int(input())
for i in range(times):
    temparr = input()
    temparr = temparr.split()
    find = int(temparr[0])
    replace = int(temparr[1])
    if find not in dicts:
        print(total)
        continue 
    if find in dicts:
        howmany = dicts[find]
        total -= howmany * find 
        total += howmany * replace 
        if replace not in dicts:
            dicts[replace] = howmany 
        else:
             dicts[replace] += howmany 
        del dicts[find]
        
        print(total)

Submission status: Accepted

Solution code:
def resolve():
    from collections import defaultdict
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    S = sum(A)
    d = defaultdict(int)
    for a in A:
        d[a] += 1

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

resolve()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
l = [list(map(int, input().split())) for _ in range(q)]
dic = Counter(a)
S = sum(a)
for i in range(q):
    (b, c) = l[i] 
    num = dic[b]
    S -= b*num
    dic[b] = 0
    if dic[c] == 0:
        dic[c] = num
    else:
        dic[c] += num
    S += c*num
    print(S)

Submission status: Accepted

Solution code:
from collections import defaultdict
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
arr = defaultdict(int)
for k, v in Counter(a).items():
    arr[k] = v
q = int(input())
bc = []
for _ in range(q):
    b, c = map(int, input().split())
    bc.append((b, c))

whole = sum([x * y for x, y in arr.items()])

for b, c in bc:
    arr[c] += arr[b]
    tmp = arr[b]
    arr[b] = 0
    whole += (c - b) * tmp
    print(whole)

Submission status: Accepted

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

for elem in a:
    if elem not in a_dic:
        a_dic[elem] = 1
    else:
        a_dic[elem] += 1

a_sum = sum(a)

for i in range(q):
    b, c = map(int,input().split())
    if b in a_dic:
        diff = c - b
        a_sum += diff * a_dic[b]
        print(a_sum)
        if c in a_dic:
            a_dic[c] += a_dic[b]
            del a_dic[b]
        else:
            a_dic[c] = a_dic[b]
            del a_dic[b]
    else:
        print(a_sum)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
temp=sum(a)
import collections
ca=collections.Counter(a)
for i in range(q):
  b,c=map(int,input().split())
  ba=ca[b]
  temp=temp-b*ba+c*ba
  print(temp)
  ca[b]=ca[b]-ba
  ca[c]=ca[c]+ba

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

# print(A)
# print(BC)
d = defaultdict(int)
sumv = sum(A)
for a in A:
    d[a] += 1
for bc in BC:
    b, c = bc
    sumv -= b * d[b]
    sumv += c * d[b]
    d[c] += d[b]
    d[b] = 0
    print(sumv)

# res = 0
# for iv in d.items():
#     i, v = iv
#     res += i*v
# print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
numl = [0] * 100005
resl = []
suma = sum(a)
for i in range(n):
    numl[a[i]]+=1
for i in range(q):
    b, c = map(int, input().split())
    bn = numl[b]
    suma += (c - b)* bn
    resl.append(suma)
    numl[b] -= bn
    numl[c] += bn
for i in resl:
    print(i)

Submission status: Accepted

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

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

ans = sum(A)
for i in range(Q):
    B, C = map(int, input().split())
    
    if B in A_dic:
        if C in A_dic:
            A_dic[C] += A_dic[B]
        else:
            A_dic[C] = A_dic[B]
        if B > C:
            ans += (C-B) * A_dic[B]
        else:
            ans -= (B-C) * A_dic[B]
        A_dic.pop(B)
    else:
        pass
    
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
Dict = {}
for i in A:
    if i not in Dict:
        Dict[i] = 1
    else:
        Dict[i]+=1
ans = sum(A)
for i in range(Q):
    B, C = map(int,input().split())
    if B in Dict and Dict[B]!=0:
        b = Dict[B]
        Dict[B]=0
        if C not in Dict:
            Dict[C]=0
        Dict[C]+=b
        
        ans+=(C-B)*b
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
A = Counter(A)
Q = int(input())
for _ in range(Q):
  B, C = map(int, input().split())
  if A.get(B):
    x = A.get(B)
    del A[B]
    if A.get(C):
      A[C] +=  x
    else:
      A[C] = x
    S += (C - B) * x
  print(S)

Submission status: Accepted

Solution code:
import collections

def resolve():
    N = int(input())
    A_list = list(map(int, input().split()))
    sum_A_list = sum(A_list)
    # 値と出現個数のリスト
    A_counter_dict = collections.Counter(A_list)
    Q = int(input())
    for i in range(Q):
        B, C = list(map(int, input().split()))
        if B in A_counter_dict.keys():
            changing_count = A_counter_dict.pop(B)
            sum_A_list += (C - B) * changing_count
            if C in A_counter_dict.keys():
                A_counter_dict[C] += changing_count
            else:
                A_counter_dict[C] = changing_count
        print(sum_A_list)

resolve()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
Ct = Counter(A)
ans = 0
for item in Ct.items():
    ans += item[0]*item[1]
for _ in range(Q):
    B, C = list(map(int, input().split()))
    B_n = Ct[B]
    ans += (C-B)*B_n
    print(ans)
    Ct[C] += Ct[B]
    Ct[B] = 0

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int,input().split()))
    q = int(input())
    from collections import Counter
    cnt = Counter(a)
    res = sum(a)
    for i in range(q):
        b, c = map(int,input().split())
        bufb = cnt[b]
        bufc = cnt[c]
        cnt[b] = 0
        cnt[c] += bufb
        res += (-b+c)*bufb
        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

dict = Counter(A)
for i in range(Q):
    l = list(map(int, input().split()))
    d = l[1] - l[0]
    cnt = dict[l[0]]
    dict[l[1]] += dict[l[0]]
    dict.pop(l[0], None)
    S += d*cnt
    print(S)

Submission status: Accepted

Solution code:
mod=pow(10,5)+2
N=int(input())
num=[0]*mod
ans=0
A=list(map(int, input().split()))
for i in range(N):
    num[A[i]]+=1
    ans+=A[i]
Q=int(input())
for i in range(Q):
    B,C=map(int, input().split())
    cnt=num[B]
    num[C]+=num[B]
    num[B]=0
    ans+=(C-B)*cnt
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
from collections import defaultdict
d = defaultdict(int)
for a in A:
  d[a]+=1
ans=sum(A)
for q 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:
from collections import Counter

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

sum = sum(a)

a = Counter(a)
a_keys = list(a.keys())
a_values = list(a.values())

for b, c in bc:
    add = a[b] * c
    red = a[b] * b
    a[c] += a[b]
    a[b] = 0
    sum = sum+add-red
    print(sum)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
l = [0] * (10**5+1)
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(len(A)):
    l[A[i]] += 1
ans = 0
for i in range(1, len(l)):
    ans += l[i]*i
for i in range(Q):
    tmp = l[B[i]]
    tmp2 = tmp * B[i]
    l[C[i]] += tmp
    tmp3 = tmp * C[i]
    l[B[i]] = 0
    ans += tmp3 - tmp2
    print(ans)

Submission status: Accepted

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

cnt = collections.Counter(a)

sum = sum(a)
sl = []
for i in range(q):
    b, c = map(int, input().split())
    bc = cnt[b]
    sum = sum - b*bc + c*bc
    sl.append(sum)

    if cnt[b] > 0:
        cnt[c] += cnt[b]
        cnt[b] = 0

for j in range(len(sl)):
    print(sl[j])

Submission status: Accepted

Solution code:


import collections

n = int(input())
a = list(map(int, input().split(" ")))
q = int(input())
have_map = collections.Counter(a)

total_cost = 0
for k,v in have_map.items():
    total_cost += k * v

for i in range(q):
    x, y = map(int, input().split(" "))
    if x in have_map:
        diff = have_map[x] * -x  + have_map[x] * y
        total_cost += diff

    have_map[y] = have_map.get(x, 0) + have_map.get(y, 0)
    have_map.pop(x, 0)

    print(total_cost)

Submission status: Accepted

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

q = int(input())
ans = sum(arr)

hashmap = {}
for val in arr:
    if val in hashmap:
        hashmap[val] += 1
    else:
        hashmap[val] = 1


while q > 0:

    [x, y] =  [int(x) for x in input().split()]
    if x in hashmap:
        if y in hashmap:
            hashmap[y] += hashmap[x]
            ans -= hashmap[x]*x
            ans += y*hashmap[x]
            del hashmap[x]
        else:
            diff = hashmap[x] * x
            ans -= diff
            hashmap[y] = hashmap[x]
            del hashmap[x]
            add = hashmap[y] * y
            ans += add
        
    print(ans)
    q -=1

Submission status: Accepted

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

zero = np.zeros(10**5+1)
total = np.sum(A)
#print(total)
for i in A:
    zero[i] += 1

for j in range(Q):
    total += (BC[j][1]-BC[j][0])*zero[BC[j][0]]
    zero[BC[j][1]] += zero[BC[j][0]]
    zero[BC[j][0]] = 0
    print(int(total))

Submission status: Accepted

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

Q = int(input())

total = sum(A)
counter = dict()

for i in range(100001):
    counter[i] = 0

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

for i in range(Q):
    b, c = map(int, input().split())
    total = total - (b * counter[b])
    total = total + (c * 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()))
d = Counter(a)
sumd = sum([k*v for k, v in d.items()])

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

for b, c in t:
   sum_minus = b * d[b]
   tmp = d.pop(b, None)
   if tmp:
      if d[c] > 0:
         d[c] += tmp
      else:
         d[c] = tmp
      sumd = sumd - sum_minus + c * tmp
   print(sumd)