Problem:


Score : 400 points

Problem Statement

You have a sequence A composed of N positive integers: A_{1}, A_{2}, \cdots, A_{N}.

You will now successively do the following Q operations:

In the i-th operation, you replace every element whose value is B_{i} with C_{i}.

For each i (1 \leq i \leq Q), find S_{i}: the sum of all elements in A just after the i-th operation.

Constraints

All values in input are integers.

 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5} 

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

N
A_{1} A_{2} \cdots A_{N}
Q
B_{1} C_{1}
B_{2} C_{2}
\vdots
B_{Q} C_{Q}

Output

Print Q integers S_{i} to Standard Output in the following format:

S_{1}
S_{2}
\vdots
S_{Q}

Note that S_{i} may not fit into a 32-bit integer.

Sample Input 1

4
1 2 3 4
3
1 2
3 4
2 4

Sample Output 1

11
12
16

Initially, the sequence A is 1,2,3,4.

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

4
1 1 1 1
3
1 2
2 1
3 5

Sample Output 2

8
4
4

Note that the sequence A may not contain an element whose value is B_{i}.

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



Sample input:
4
1 2 3 4
3
1 2
3 4
2 4


Sample output:
11
12
16

Submission status: Accepted

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

P = [0]*100001
sumA = sum(A)

for i in range (0, N):
	P[A[i]]+=1

Q = int(input())

for i in range (0, Q):
	B, C = map(int, input().split())
	if P[B] > 0:
		sumA+=(C-B)*P[B]
		P[C]+=P[B]
		P[B] = 0
		print(sumA)
	else:
		print(sumA)

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

samu = sum(a)
num = [0 for i in range(10**5)]
for i in range(n):
    nu = a[i]
    num[nu-1] += 1

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

Submission status: Accepted

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

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

'''
a=[]
b=[]
for i in range():
    A, B = map(int, input().split())
    a.append(A)   
    b.append(B)'''

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

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

from collections import Counter
su=sum(a)
a=Counter(a)
#print(a)

for i in range(q):
    a[c[i]]+=a[b[i]]
    su+=(c[i]*a[b[i]]-b[i]*a[b[i]])

    a[b[i]]=0
    print(su)
#print(sum(a))

Submission status: Accepted

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
from collections import Counter
import sys
def main(N, A, Q, BC):
    C = Counter(A)
    s = sum(A)
    for b, c in BC:
        bc = C[b]
        bs = b * bc
        cs = c * bc
        s += cs - bs
        C[b] = 0
        C[c] += bc
        print(s)

if __name__ == '__main__':
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    Q = int(input())
    BC = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, A, Q, BC)

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
Q=int(input())

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

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

ans=sum(A)

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

Submission status: Accepted

Solution code:
import glob
import os

bn = os.path.basename(__file__).split('.')[0]
dn = os.path.dirname(__file__).split('/')

# 問題ごとのディレクトリのトップからの相対パス
REL_PATH = dn[len(dn)-2] + '\\' + dn[len(dn)-1] + '\\' + bn

# テスト用ファイル置き場のトップ
TOP_PATH = 'C:\\AtCoder'

class Common:

    problem = []
    index = 0

    def __init__(self, rel_path):
        self.rel_path = rel_path

    def initialize(self, path):
        file = open(path)
        self.problem = file.readlines()
        self.index = 0
        return

    def input_data(self):
        try:
            IS_TEST
            self.index += 1
            return self.problem[self.index-1]

        except NameError:
            return input()

    def resolve(self):
        pass

    def exec_resolve(self):
        try:
            IS_TEST
            for path in glob.glob(TOP_PATH + '\\' + self.rel_path + '/*.txt'):
                print("Test: " + path)
                self.initialize(path)
                self.resolve()
                print("\n\n")
        except NameError:
            self.resolve()


class Solver(Common):

    def resolve(self):

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

        num_count = [0] * (100000+1)

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

        result = 0
        for i in range(100000+1):
            result += num_count[i] * i

        for i in range(Q):
            result += (C[i] - B[i]) * num_count[B[i]]
            num_count[C[i]] += num_count[B[i]]
            num_count[B[i]] = 0
            print(str(result))

solver = Solver(REL_PATH)
solver.exec_resolve()

Submission status: Accepted

Solution code:
import collections

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

A_counter = collections.Counter(A)
ans = sum(A)

for q in range(Q):
    B,C=map(int, input().split())
#    B,C=map(int, f.readline().split())
#    B_count = A_counter.pop(B)
    B_count = A_counter[B]
    A_counter[B]=0
    A_counter[C] += B_count
    ans += (C-B)*B_count
    print(ans)

Submission status: Accepted

Solution code:
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
Q = int(readline())
sum = sum(A)
d = [0]*(10**5+1)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
#from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
#from copy import deepcopy
#from collections import deque
#import numba

def run():
    N = int(sysread())
    A = list(map(int, sysread().split()))
    Q = int(sysread())
    stocks = [0 for _ in range(10** 5 + 1)]
    total = 0
    for a in A:
        stocks[a] += 1
        total += a

    for _ in range(Q):
        b,c = map(int, sysread().split())
        stocks[c] += stocks[b]
        total += c * stocks[b]
        total -= b * stocks[b]
        stocks[b] = 0
        print(total)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(hoge) for hoge in input().split()]
kazu = [0] * (100001)
for a in A:
    kazu[a] += 1
S = sum(A)
C = Counter(A)
Dic = dict(C)
Q = int(input())
for q in range(Q):
    B,C = [int(hoge) for hoge in input().split()]
    K = kazu[B]
    S += K*(C-B)
    kazu[B] = 0
    kazu[C] += K
    print(S)

Submission status: Accepted

Solution code:
import collections

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

ans = sum(A)

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

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
Q = int(stdin.readline().rstrip())
ans = sum(A)
cnt = Counter(A)

for i in range(Q):
    B,C = [int(x) for x in stdin.readline().rstrip().split()]
    cnt_b = cnt[B]
    cnt_c = cnt[C]
    if B <= C:
        ans += cnt_b*(C-B)
        print(ans)
    else:
        ans -= cnt_b*(B-C)
        print(ans)

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

Submission status: Accepted

Solution code:
n = input()

arr = [int(x) for x in input().split()]
d = {}
s = sum(arr)
for num in arr:
  d[num] = d.get(num,0) + 1
  
q = int(input())
while q > 0:
  a, b = map(int, input().split())
  if a not in d:
    print(s)
    q -= 1
    continue
  s = s - d[a]*a + d[a]*b
  d[b] = d.get(b,0) + d[a]
  d[a] = 0
  print( s )
  q -= 1

Submission status: Accepted

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

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

d = defaultdict(int)

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

for b, c in bc:
    nb = d[b]
    nc = d[c]
    s += (c - b) * nb
    print(s)
    d[b] = 0
    d[c] += nb

Submission status: Accepted

Solution code:
from math import *
from collections import *
from itertools import *
from bisect import *
from heapq import *
from operator import *
from sys import *
setrecursionlimit(100000000)


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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]

    d = dict()
    for a in A:
        if a in d:
            d[a] += 1
        else:
            d[a] = 1

    total = sum(A)
    ans = []
    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().split())
        if b in d:
            if c in d:
                d[c] += d[b]
            else:
                d[c] = d[b]

            total += (c - b) * d[b]
            ans.append(total)
            d.pop(b)

        else:
            ans.append(total)

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

n = int(input())
A = list(map(int,input().split()))
counter = collections.Counter(A)
_sum = sum(A)

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

Submission status: Accepted

Solution code:
import collections

n = int(input())

a = list(map(int, input().split()))
total = sum(a)
aa = collections.Counter(a)
q = int(input())

for i in range(q):
    b, c = map(int, input().split())
    if b in aa and c in aa:
        total += c * aa[b] - b * aa[b]
        print(total)
        aa[c] += aa[b]
        aa.pop(b)
    elif b in aa:
        total += c * aa[b] - b * aa[b]
        print(total)
        aa[c] = aa[b]
        aa.pop(b)
    else:
        print(total)

Submission status: Accepted

Solution code:
n=int(input())
member = [0]*(10**5+1)
 
li = list(map(int,input().split()))
total = sum(li)
for i in range(n):
  member[li[i]] +=1
 
q = int(input())
for j in range(q):
  x,y = input().split()
  x=int(x)
  y=int(y)
  total += (y-x)*member[x]
  print(total)
  member[y]+=member[x]
  member[x]=0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())
B = []
C = []
for q in range(Q):
    x, y = [int(i) for i in input().split()]
    B.append(x)
    C.append(y)

S = [0] * (Q + 1)
S[0] = sum(A)

AA = {}

for a in A:
    if a in AA:
        AA[a] += 1
    else:
        AA[a] = 1

def my_sum(dic):
    sum = 0
    for k, v in dic.items():
        sum += k * v
    return sum

for q in range(1, Q+1):
    if B[q-1] not in AA:
        S[q] = S[q-1]
        continue
    S[q] = S[q-1] - B[q-1] * AA[B[q-1]]

    S[q] += C[q-1] * AA[B[q-1]]

    if C[q-1] in AA:
        AA[C[q-1]] += AA[B[q-1]]
        AA[B[q-1]] = 0
    else:
        AA[C[q-1]] = AA[B[q-1]]
        AA[B[q-1]] = 0

for q in range(1, Q+1):
    print(S[q])

Submission status: Accepted

Solution code:
import re
def main():
    n = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    BC = [list(map(int,input().split())) for _ in range(Q)]
    dic = [0]*(10**5 + 1)
    sm = 0
    for a in A:
        dic[a] += 1
        sm += a
    
    for b,c in BC:
        num = dic[b]
        dic[c] += dic[b]
        dic[b] = 0
        sm = sm - num*b + num*c
        print(sm)
    return 

if __name__ == "__main__":
    main()

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

dic = {}
ans = sum(a)


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


for b,c in bc:
    try:
        before = dic[b]
    except:
        before = 0

    ans = ans + before * (c-b)
    print(ans)
    try:
        dic.pop(b)
    except:
        pass

    if c in dic:
        dic[c] += before
    else:
        dic[c] = before

Submission status: Accepted

Solution code:
import numpy as np
def resolve():
    N = int(input())
    A = list(input().split())
    
    A_all = np.zeros(10**5 + 1, dtype=int)
    A_calc = range(10**5 + 1)
    for i in range(N):
        A_all[int(A[i])] += 1
    ans = sum(A_all * A_calc)
    
    Q = int(input())
    for i in range(Q):
        B,C = map(int,input().split())
        ans = ans + C * A_all[B] - B * A_all[B]
        print(ans)
        A_all[C] += A_all[B]
        A_all[B] = 0
resolve()

Submission status: Accepted

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

ans = sum(a)

q = int(input())

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

Submission status: Accepted

Solution code:
import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]

from collections import Counter
N = ri()
A = ri_()
S = sum(A)
C = Counter(A)
Q = ri()
for _ in range(Q):
    b, c = ri_()
    d = C[b] * c - C[b] * b 
    C[c] += C[b]
    C[b] = 0
    S += d
    print(S)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

N = int(input())
A = sorted(list(map(int, input().split())))
sum_ = sum(A)
cntA = dict(Counter(A))

Q = int(input())
map_values = {val: val for val in set(A)}
for _ in range(Q):
    B, C = map(int, sys.stdin.readline().split())
    sum_ += (C-B) * cntA.get(B, 0)

    if C in cntA:
        cntA[C] += cntA.get(B, 0)
    else:
        cntA[C] = cntA.get(B, 0)
    cntA[B] = 0
    print(sum_)

Submission status: Accepted

Solution code:
from collections import defaultdict as mapp
vis=mapp(lambda:0)
x=int(input())
s=list(map(int,input().split()))
for n in s:
    vis[n]+=1

sm=sum(s)
y=int(input())
for n in range(y):
    a,b=map(int,input().split())
    p=vis[a]
    vis[a]=0
    vis[b]+=p
    sm-=p*a
    sm+=p*b
    print(sm)

Submission status: Accepted

Solution code:
from decimal import *

n=int(input())
l=list(map(int, input().split(' ')))
q=int(input())
freqs=[]
add=Decimal(0)
for i in l:
    if i>=len(freqs):
        freqs+=(i-len(freqs)+1)*[0]
    freqs[i]+=1
    add+=i

        
for i in range(q):
    b,c=map(int, input().split(' '))
    if b<len(freqs):
        add+=Decimal((c-b)*(freqs[b]))
        if c>=len(freqs):
            freqs+=(c-len(freqs)+1)*[0]
        freqs[c]+=freqs[b]
        freqs[b]=0
    print(add)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

ct = [0 for i in range(10**5+1)]

ans = 0
for a  in arr:
    ct[a] += 1
    ans += a

q = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
d = dict()

N = int(input())
A = [int(_) for _ in input().split()]
Q = int(input())

val = sum(A)
ans = []
for a in A:
    if a in d:
        d[a] += 1
    else:
        d[a] = 1

for q in range(Q):
    b, c = [int(_) for _ in input().split()]
    if b not in d:
        ans.append(val)
        continue
    x = d.pop(b)
    if c in d:
        d[c] += x
    else:
        d[c] = x
    val += (c-b) * x    
    ans.append(val)

for v in ans:
    print(v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
from collections import defaultdict #d = defaultdict(int) d[key] += value
from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()
Q = ii()
B = li2(Q)

#a =　dict(Counter(A).most_common())
a = defaultdict(int)
for num in A:
    a[num] += 1
#print(a)
ans = sum(A)
for i in range(Q):
    if a[B[i][0]]:
        #print(a[B[i][1]])
        ans += (B[i][1]-B[i][0]) * a[B[i][0]]
        a[B[i][1]] += a[B[i][0]]
        a[B[i][0]] = 0
        print(ans)
    else:
        print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
a_dict = {}
for a in A:
  if a in a_dict.keys():
    a_dict[a] += 1
  else:
    a_dict[a] = 1
ans = sum(A)
Q = int(input())
for i in range(Q):
  b, c = map(int, input().split())
  if not(b in a_dict.keys()):
    print(ans)
    continue
  num = a_dict.pop(b)
  ans += (c - b)*num
  print(ans)
  if c in a_dict.keys():
    a_dict[c] += num
  else:
    a_dict[c] = num

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

cnt = 0
l = [0]*(10**5+1)
for v in A:
    l[v] += 1
    cnt += v

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)

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

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

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

CNT = defaultdict(int)

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

TOTAL = sum(A)

ANS = []
for b, c in QUERY:
    TOTAL += (c - b) * CNT[b]
    CNT[c] += CNT[b]
    CNT[b] = 0
    ANS.append(TOTAL)

print("\n".join(map(str, ANS)))

Submission status: Accepted

Solution code:
import sys

N = int(input())
A = list(map(int, sys.stdin.readline().strip().split()))

# 各数字の個数を記録するリスト alpha
alpha = [0] * 10 ** 5
for a in A:
    alpha[a - 1] += 1

# beta = [i for i in range(1, 10 ** 5 + 1)]

ans = sum(A)
Q = int(input())
for q in range(Q):
    B, C = map(int, sys.stdin.readline().strip().split())
    # beta[B - 1] = C

    # print(f'alpha : {alpha[B - 1]}')
    # print(f'add: {alpha[B - 1] * (C - B)}')

    ans += alpha[B - 1] * (C - B)

    alpha[C - 1] += alpha[B - 1]
    alpha[B - 1] = 0
    # ans = ans + alpha[B - 1] * (C - B)
    print(ans)

Submission status: Accepted

Solution code:
import sys, collections, bisect, itertools, heapq, math, copy
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = LI()
    A = LI()
    Q = I()
    BC = [LI() for _ in range(Q)]

    cnt = collections.Counter(A)
    S = sum([k*v for k, v in cnt.items()])

    for i in BC:
        B = i[0]
        C = i[1]
        if B in cnt:
            B_num = cnt[B]
            if C in cnt.keys():
                cnt[C] += B_num
            else:
                cnt[C] = B_num
            S += (C - B) * B_num
            cnt.pop(B)
        print(S)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

ans = 0
for k, v in a.items():
    ans+=k*v

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

        ans+=c*temp
        a[c]+=temp
        print(ans)
    else:
        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

dic = Counter(A)

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)
dic = {}
for i in range(N):
    if a[i] in dic:
        dic[a[i]] += 1
    else:
        dic[a[i]] = 1
for _ in range(q):
    b, c = map(int, input().split())
    if b in dic:
        s = s + (c-b)*dic[b]
        print(s)
        if c in dic:
            dic[c] += dic[b]
        else:
            dic[c] = dic[b]
        del dic[b]
    else:
        print(s)

Submission status: Accepted

Solution code:
N = int( input() )
A = list( map( int, input().split()))
L = [ 0 ] * ( 10 ** 5 )

for a in A:
  L[ a - 1 ] += 1
SumA = sum( A )

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

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
N = int(input())
A = [int(i) for i in input().split()]
C = Counter(A)
Q = int(input())

S = sum(A)

for i in range(Q):
    s, t = [int(i) for i in input().split()]
    S += (t-s)*C[s]
    C[t] += C[s]
    C[s] = 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)]

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

s = 0
for a in A:
    s += a

for bc in BC:
    b, c = bc
    if b in nums:
        num = nums[b]
        nums[b] = 0
        nums.setdefault(c, 0)
        nums[c] += num
        s += (c-b)*num
    print(s)

Submission status: Accepted

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

sum_alist=sum(alist)
adic=defaultdict(int)
for a in alist:
  adic[a]+=1

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

Submission status: Accepted

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

ans = sum(a)
from collections import Counter
cnt = Counter(a)

for i, j in s:
    #ans = ans - i * cnt[i] + j * cnt[j]
    if j in cnt:
        cnt[j] += cnt[i]
    else:
        cnt[j] = cnt[i]
        
    ans = ans - i * cnt[i] + cnt[i] * j
    if i in cnt:
        cnt.pop(i)
    #ans = ans + j * cnt[j]
    #print(ans, cnt)
    print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし

from collections import Counter

N = I()
A = LI()
sum = sum(A)
a = Counter(A)

Q = I()
for i in range(Q):
    b,c = LI()
    sum += a[b]*(c-b)
    print(sum)
    a[c] += a[b]
    a[b] = 0

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Q = int(input())

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

s = sum(A)
ans = []
for i in range(Q):
    a, b = map(int, input().split())

    s = s - a * count[a-1] + b * count[a-1]
    ans.append(s)
    count[b-1] += count[a-1]
    count[a-1] = 0

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
c = collections.Counter(A)
Q = int(input())
ans = sum(A)
for q in range(Q):
  B, C = map(int, input().split())
  count = c[B]
  c[B] -= count
  c[C] += count
  ans += (C-B)*count
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

n = int(input())
a = lmp()
q = int(input())
num = [0]*(10**5+1)
ans = sum(a)
for i in range(n):
    num[a[i]] += 1
for i in range(q):
    b,c = mp()
    ans -= b*num[b]
    ans += c*num[b]
    print(ans)
    num[c] += num[b]
    num[b] = 0

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import collections

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B, C = [], []
for q in range(Q):
    B_q, C_q = list(map(int, input().split()))
    B.append(B_q)
    C.append(C_q)

# 求解処理
S = sum(A)
counter_A = collections.Counter(A)
for b, c in zip(B, C):
    S += (c - b) * counter_A[b]
    # 結果出力
    print(S)
    # カウンターの更新
    counter_A[c] += counter_A[b]
    counter_A[b] = 0

Submission status: Accepted

Solution code:
from math import *
from collections import *
n=int(input())
a=list(map(int,input().split()))
f=Counter(a)
q=int(input())
r=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    re=f[b]
    del f[b]
    if(c in f):
        f[c]+=re
    else:
        f[c]=re
    r+=(c-b)*re
    print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
c=list(map(int,input().split()))
q=int(input())
su=0
d=[]
for i in range(1000003):
	d.append(0)
for i in range(len(c)):
	d[c[i]]=d[c[i]]+1
	su=su+c[i]
for j in range(q):
	r,s=map(int,input().split())
	su=su-d[r]*r+d[r]*s
	d[s]=d[s]+d[r]
	d[r]=0
	print(su)

Submission status: Accepted

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

bu = [0] * (10**5+10)

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

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