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 collections

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

# aの中の各要素のカウント
c = collections.Counter(a)

ans = sum(a)
for i in range(q):
  ans += (bc[i][1] - bc[i][0]) * c[bc[i][0]]
  c[bc[i][1]] += c[bc[i][0]]
  c[bc[i][0]]  = 0
  print(ans)

Submission status: Accepted

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

s = sum(la)

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

for i in lq:
    s += (i[1] - i[0]) * num[i[0] - 1]
    num[i[1] - 1] += num[i[0] - 1]
    num[i[0] - 1] = 0
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
a_dict = {}
for i in a:
  if i not in a_dict:
    a_dict[i] = 1
  else:
    a_dict[i] += 1

q = int(input())

replace = []
for _ in range(q):
  m, n = [int(i) for i in input().split()]
  replace.append((m,n))

res = sum([m*n for m,n in a_dict.items()])

for r in replace:
  if r[0] in a_dict:
    res += (r[1] - r[0])*a_dict[r[0]]
    
    if r[1] in a_dict:
      a_dict[r[1]] += a_dict[r[0]]
    else:
      a_dict[r[1]] = a_dict[r[0]]
    a_dict[r[0]] = 0

  print(res)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
nums = list(map(int, input().split()))
q = int(input())
vals = [tuple(map(int, input().split())) for _ in range(q)]

c = Counter(nums)
total = sum([x*y for x, y in c.items()])
for b, k in vals:
    o = c[b]
    del c[b]
    c[k] += o
    total += k * o - b * o
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter


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

dic = Counter(a)

ans = sum(a)
for i in range(q):
    b, c = map(int,input().split())
    if b in dic.keys():
        if c in dic.keys():
            dic[c] += dic[b]
            ans += (c - b) * dic[b]
            del dic[b]
        else:
            dic[c] = dic[b]
            ans += (c - b) * dic[b]
            del dic[b]
    
    print(ans)

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)

kosu = collections.Counter(a)
s = sum(a)
for i in range(q):

    x = kosu[b[i]]

    s += x * (c[i] - b[i])

    if c[i] in kosu.keys():
        kosu[c[i]] += x
    else:
        kosu.update(
            {c[i]: x}
        )
    kosu[b[i]] = 0

    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = sum(A)
d = {}
for i in range(N):
    if A[i] not in d:
        d[A[i]] = 1
    else:
        d[A[i]] += 1
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    if B in d:
        ans += (C-B) * d[B]
        if C in d:
            d[C] += d[B]
            d[B] = 0
        else:
            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()))
Ac = Counter(A)
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)
for i in range(q):
    if B[i] in Ac:
        num = Ac[B[i]]
        #print("num", num)
        if C[i] in Ac:
            Ac[C[i]] += Ac[B[i]]
        else:
            Ac[C[i]] = Ac[B[i]]
        del Ac[B[i]]
        s += (-B[i] + C[i]) * num
    print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
A=list(map(int,input().split()))
q=int(input())
b=[]
c=[]
for i in range(q):
    bbuf,cbuf = map(int,input().split())
    b.append(bbuf)
    c.append(cbuf)

d=defaultdict(int)
t=0
for a in A:
    d[a]+=1
    t+=a
for i in range(q):
    be=b[i]
    af=c[i]
    t+=af*d[be]-be*d[be]
    d[af]+=d[be]
    d[be]=0
    print(t)

Submission status: Accepted

Solution code:
def main():
  N = int(input())
  A = list(map(int, input().split()))
  Q = int(input())
  num = [0] * 100005
  for i in A:
    num[i] += 1
  ans = sum(A)
  for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b)*num[b]
    print(ans)
    num[c] += num[b]
    num[b] = 0
  
if __name__ == "__main__":
  main()

Submission status: Accepted

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

# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    a_list = input_to_int_tuple()
    q = input_int()
    bc = [input_to_int_tuple() for i in range(q)]

    from collections import defaultdict
    a_cnt = defaultdict(int)
    for i in a_list:
        a_cnt[i] += 1

    a_sum = sum(a_list)

    ret = a_sum
    for b, c in bc:
        sa = c - b
        b_cnt = a_cnt.get(b, 0)
        c_cnt = a_cnt.get(c, 0)
        a_cnt[b] = 0
        a_cnt[c] = b_cnt + c_cnt
        ret += (sa * b_cnt)
        print(ret)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop
import math
import bisect
input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

co = defaultdict(int)

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
c = []

for a_ in a:
    co[a_] += 1
# print(co)

ans = sum(a)

for _ in range(q):
    b_, c_ = map(int, input().split())
    b.append(b_)
    c.append(c_)

    diff = - co[b_] * b_
    diff += co[b_] * c_
    co[c_] += co[b_]
    co[b_] = 0
    ans += diff
    print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input(): return sys.stdin.readline().rstrip()

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

    cnt = Counter(A)
    sum_v = sum(A)
    for _ in range(Q):
        b, c = map(int, input().split())

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    num = [0] * (1 + 10**5)
    ans = 0
    for a in A:
        num[a] += 1
        ans += a

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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


dict = defaultdict(lambda: 0)
sum = 0

for a in A:
    dict[a] += 1
    sum += a

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

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

o = [0] * 100010

for i in range(n):
    o[a[i]] += 1
#print(o)
ans = sum(a)
for i in range(q):
    ans += o[b[i]]*(c[i] - b[i])
    print(ans)
    o[c[i]] += o[b[i]]
    o[b[i]] = 0
    #print(sum(o))

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
dp=[0 for i in range(110000)]

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

S=sum(A)

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

Submission status: Accepted

Solution code:
N=int(input())
ls=[int(s) for s in input().split()]
dic={}
for k in ls:
  if k in dic:
    dic[k]+=1
  else:
    dic[k]=1
#print(dic)
_sum=0
for k,v in dic.items():
  _sum+=k*v
#print(_sum)
K=int(input())
for _ in range(K):
  b,c=[int(s) for s in input().split()]
  if b in dic:
    _sum+=(c-b)*dic[b]
    if c in dic:
      dic[c]+=dic[b]
    else:
      dic[c]=dic[b]
    dic[b]=0
  print(_sum)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(AList)

result = sum(AList)
resultList = []
for i in range(Q):
    B, C = map(int, input().split())
    tmp = C - B
    
    result += tmp * c[B]
    
    c[C] += c[B]
    c[B] = 0
    
    resultList.append(result)

for i in range(len(resultList)):
    print(resultList[i])

Submission status: Accepted

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

Submission status: Accepted

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

from collections import defaultdict

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

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

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

Submission status: Accepted

Solution code:
import collections

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

d = collections.Counter(a)
s = 0
for k, v in d.items():
    s += int(k) * v

for i in range(q):
    b, c = bc[i]
    s += (int(c) - int(b)) * d[b]
    print(s)
    if c in d.keys():
        d[c] += d[b]
        d[b] = 0
    else:
        d[c] = d[b]
        d[b] = 0

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

x = Counter(a)
ans = sum(a)
for b, c in bc:
    ans += (c - b) * x[b]
    print(ans)
    x[c] += x[b]
    x[b] = 0

Submission status: Accepted

Solution code:
import collections

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

Ali_counter = collections.Counter(Ali)

sum_ans = sum(Ali)
for b, c in BCli:
    sum_ans = sum_ans + (Ali_counter[b] * (c-b))
    print(sum_ans)
    Ali_counter[c] = Ali_counter[c] + Ali_counter[b]
    Ali_counter[b] = 0

Submission status: Accepted

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

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys
import bisect

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
INF = float('inf')


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

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

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

current_sum = sum(A)

for b, c in query:
    if b in dict_A:
        diff = c * dict_A[b] - b * dict_A[b]
        current_sum += diff
        dict_A[c] += dict_A[b]
        dict_A[b] = 0
    print(current_sum)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
ans = sum(a)
b = [str(i) for i in a]
q = int(input())
rep = [list(map(int,input().split())) for _ in range(q)]
now = [0 for i in range(10**5+1)]

c = Counter(b).most_common()
for i in range(len(c)):
    now[int(c[i][0])] = c[i][1]
for i in range(q):
    ans = ans - rep[i][0]*now[rep[i][0]] + rep[i][1]*now[rep[i][0]]
    now[rep[i][1]] += now[rep[i][0]]
    now[rep[i][0]] = 0
    print(ans)

Submission status: Accepted

Solution code:
import collections

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

num_dict = dict(collections.Counter(a))
tmp_sum=sum(a)
#print(num_dict,tmp_sum)

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
*A, = map(int, input().split())
cnt = Counter(A)
ans = []
S = sum(A)
Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    S += c * cnt[b] - b * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    ans.append(S)
print(*ans, sep='\n')

Submission status: Accepted

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

adhoc=sum(A_ls)
import collections
A_dict=collections.Counter(A_ls)

for wamimiavioawmifwe in range(Q):
	B,C=map(int, input().split())
	adhoc=adhoc+A_dict[B]*(C-B)
	A_dict[C]+=A_dict[B]
	A_dict[B]=0
	print(adhoc)


# 2darray [[0] * 4 for i in range(3)]

Submission status: Accepted

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

num = [0]*(10**5+1)
#num = [0]*100000  #後で変える
S = []

#1 iterlation
S.append(sum(A))
#print('S0:', S[0])  #############
for i in range(N):
    num[A[i]]+=1
#print('num0:', num)  ########

for j in range(Q):
    if num[BC[j][0]] != 0:
        B = BC[j][0]
        C = BC[j][1]
        #print('B,C:', B,C)  ##########
        S.append(S[-1] + (C - B)*num[B] )
        #num[B] -=1
        dammy = num[B]
        num[B] = 0
        num[C] += dammy
        #print('num:', num)  ########
        #print('S:',S)   #############

    else:
        B = BC[j][0]
        C = BC[j][1]
        #print('B,C:', B,C)  ##########
        #print('yaaaaaah')  ########
        S.append(S[-1])
        #print('S:',S)   ##########


#print('finalS:', S)   #############

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#import numpy as np
#from decimal import *


N = INT()
A = LIST()
Q = INT()

ans = sum(A)
dic = defaultdict(int)

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

for _ in range(Q):
	B, C = MAP()
	ans += (C-B)*dic[B]
	print(ans)
	dic[C] += dic[B]
	dic[B] = 0

Submission status: Accepted

Solution code:
from collections import Counter

N,*f = map(int, open(0).read().split())
A = f[:N]
Q = f[N]
BC = [f[N+i*2+1:N+i*2+3] for i in range(Q)]
c = Counter(A)
ans = sum(A)
for B, C in BC:
    if c[B] > 0:
        if c[C] > 0:
            ans += (C-B) * c[B]
            c[C] += c.pop(B)
        else:
            ans += (C-B) * c[B]
            c[C] = c.pop(B)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = sum(a)
A = Counter(a)
for _ in range(int(input())):
    b, c = map(int, input().split())
    val = A[b]
    del A[b]
    A.setdefault(c, 0)
    A[c] += val
    ans = ans - b * val + c * val
    print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
n=int(input())
a=sorted(list(map(int,input().split())))
q=int(input())
A=collections.Counter(a)
ans=sum(a)
for _ in range(q):
  b,c=map(int,input().split())
  k=A[b]
  ans=(c-b)*k+ans
  print(ans)
  del A[b]
  A[c]+=k

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-
n = int(input())
a_list = list(map(int, input().split()))
a_dict = {}
total = 0
for a in a_list:
    if a in a_dict:
        a_dict[a] += 1
    else:
        a_dict[a] = 1
    total += a

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

Submission status: Accepted

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

from collections import Counter
count = Counter(a)

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

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

for i in range(Q):
  sums-=nums[BC[i][0]]*BC[i][0]
  sums+=nums[BC[i][0]]*BC[i][1]
  print(sums)
  nums[BC[i][1]]+=nums[BC[i][0]]
  nums[BC[i][0]]=0

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

num=sum(A)
N={}
for i in A:
   if i not in N:N[i]=0
   N[i] +=1

for b,c in BC:
    if b not in N:
        print(num)
        continue
    dig=c-b
    num +=dig*N[b]
    print(num)
    if c not in N:N[c]=0
    N[c] +=N[b]
    N[b]=0

Submission status: Accepted

Solution code:
counter = [0]*(10**5)
sum = 0
ans = []
N = int(input())
number = list(int(x) for x in input().split())
for i in number:
    sum += i
    counter[i-1] += 1
Q = int(input())
for i in range(Q):
    B, C = (int(x) for x in input().split())
    # sum計算
    count = counter[B-1]
    sum -= B * count
    sum += C * count
    ans.append(sum)
    # counter処理
    counter[B-1] = 0
    counter[C-1] += count
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
b = []
c = []
for i in range(q):
    x, y = map(int, input().split())
    b.append(x)
    c.append(y)

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

s = sum(a)

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
cnt = Counter(map(int, input().split()))
q = int(input())
Asum = sum(k*v for k, v in cnt.items())
for _ in range(q):
    b, c = map(int, input().split())
    cnt[c] += cnt[b]
    Asum += c*cnt[b]-b*cnt[b]
    cnt[b] = 0
    print(Asum)

Submission status: Accepted

Solution code:
def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N = II()
    A = LMIIS()
    Q = II()
    counter = Counter(A)

    tmpsum = sum(A)
    ans = deque()
    
    for i in range(Q):
        b,c = LMIIS()
        num_b = counter[b]
        counter[b] = 0
        counter[c] += num_b
        tmpsum += num_b*(c-b)
        ans.append(tmpsum)
    for a in ans:
        print(a)



    # change_from = dict()
    # change_to = dict()
    # for i in range(Q):
    #     b,c = LMIIS()
    #     #変化後にbになっているものの変化先をcに変える
    #     if not b in change_from.keys():
    #         change_from[b] = b
    #     change_to[change_from[b]] = c
    #     change_to[b] = c
    #     change_from[c] = b
    

    # for a in A:
    #     if not a in change_to.keys():
    #         print(a)
    #     else:
    #         print(change_to[a])
    
main()

Submission status: Accepted

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

# ans=0
# for k,v in d.items():
#   ans+=k*v
# print(ans)

Submission status: Accepted

Solution code:
# Template 1.0
import sys, re
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

n = INT()

a = LIST()

dd =defaultdict(int)

for el in a:
    dd[el]+=1

q = INT()

ans = sum(a)

while(q!=0):
    b, c = MAP()

    ans+=dd[b]*c - dd[b]*b

    dd[c]+=dd[b]
    dd[b] = 0

    print(ans)

    q-=1

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
total = sum(a)
mem = [0]*(100000+1)
for v in a:
    mem[v] += 1
while q>0:
    b,c = map(int, input().split())
    total -= b*mem[b]
    mem[c] += mem[b]
    total += c*mem[b]
    mem[b] = 0
    print(total)
    q -= 1

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)]
ans=sum(a)
from collections import Counter
ca=Counter(a)
for b,c in bc:
  if b in ca:
    ca[c]+=ca[b]
    ans+=(c-b)*ca[b]
    ca[b]=0
    print(ans)
  else:
    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 A:
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1
for i in range(Q):
    B,C=map(int,input().split())
    if B in dic:
        x=dic[B]
        dic[B]=0
        if C in dic:
            dic[C]+=x
        else:
            dic[C]=x
        dif=C-B
        dif=dif*x
        S+=dif
    print(S)

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())
A = [int(i) for i in input().split()]
Q = int(input())
BC = []

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

sums = [0] * 100001

init_sum = sum(A)
for a in A:
    sums[a] += 1

for res in BC:
    sums[res[1]] += sums[res[0]]
    init_sum += (res[1] - res[0]) * sums[res[0]]
    sums[res[0]] = 0
    print(init_sum)

Submission status: Accepted

Solution code:
import collections

n = int(input())

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

q = int(input())

num_dict = dict(collections.Counter(a))

temp = [key * value for key, value in num_dict.items()]

ans = sum(temp)

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

    if num_dict.get(b):
        num_dict[c] = num_dict[b] + num_dict.get(c, default=0)

        ans = ans - num_dict[b] * b + num_dict[b] * c

        del(num_dict[b])

    print(ans)

Submission status: Accepted

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

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

q = int(input())

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Ad={}
for a in A:
  if a not in Ad:
    Ad[a]=1
  else:
    Ad[a]+=1
sum_A=sum(A)

Q=int(input())
for q in range(Q):
  B,C=map(int,input().split())
  if B in Ad:
    sum_A-=B*Ad[B]
    sum_A+=C*Ad[B]
    if C in Ad:
      Ad[C]+=Ad[B]
    else:
      Ad[C]=Ad[B]
    Ad[B]=0
    pass
  print(sum_A)

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)]
memo=[0]*100001
ans=0
for i in range(n):
    ans+=a[i]
    memo[a[i]-1]+=1
for i in range(q):
    memo[bc[i][1]-1]+=memo[bc[i][0]-1]
    ans+=memo[bc[i][0]-1]*(bc[i][1]-bc[i][0])
    memo[bc[i][0]-1]=0
    print(ans)

Submission status: Accepted

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


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    from collections import defaultdict
    X = defaultdict(int)
    for a in A:
        X[a] += 1
    ret = sum(A)
    for b, c in zip(B, C):
        ret -= b * X[b]
        ret += c * X[b]
        X[c] += X[b]
        del X[b]
        print(ret)

# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
def LN(n):return [N() for i in range(n)]
def LL(n):return [L() for i in range(n)]
n=N()
l=L()
q=N()
ans=sum(l)
import collections
c=collections.Counter(l)
for i in range(q):
    B,C=NM()
    bi=c[B]
    ans+=bi*(C-B)
    print(ans)
    c[B]=0
    c[C]+=bi

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
a_sum = sum(a)
a_count = Counter(a)

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

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


dic = {}

sum_ = 0
for a in A:
    if a in dic:
        dic[a] += 1
    else:
        dic[a] = 1

    sum_ += a


for b, c in BC:
    if b in dic:
        x = dic[b]
    else:
        print(sum_)
        continue

    sum_ += x * (c - b)
    print(sum_)

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

    dic[b] -= x

Submission status: Accepted

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

c = Counter(target_ls)
num_replace = int(input())
ans_ls = [0] * num_replace
for i in range(num_replace):
    before_value, after_value = map(int,input().split())
    before_times = c[before_value]
    c[after_value] += before_times
    c[before_value] = 0
    ans -= before_times * before_value
    ans += before_times * after_value 
    ans_ls[i] = ans
for i in range(num_replace):
    print(ans_ls[i])

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    # 整数 1 つ
    n = int(input())
    A = list(map(int, input().split()))
    # 整数複数個
    # a, b = map(int, input().split())
    # 整数 N 個 (改行区切り)
    # N = [int(input()) for i in range(N)]
    # 整数 N 個 (スペース区切り)
    #A = list(map(int, input().split()))
    # 整数 (縦 H 横 W の行列)
    #BC = [list(map(int, input().split())) for i in range(q)]

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

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

resolve()