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:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
a = Counter(a)
sum_a = 0
for k,v in a.items():
    sum_a += k*v
for i in range(q):
    b,c = map(int,input().split())
    a[c] += a[b]
    sum_a += (c-b)*a[b]
    a[b] = 0
    print(sum_a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC_List = x = [list(map(int, input().split())) for i in range(Q)]
int_list = [0 for _ in range(10**5+1)]
sum = 0
for i in A:
    int_list[i] += 1
    sum += i

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

Submission status: Accepted

Solution code:
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)]
c = dict(collections.Counter(A))
S = sum(A)
for i in range(Q):
    [B, C] = BC[i]
    if B in c.keys():
        S = S+(C-B)*c[B]
        print(S)
        if C in c.keys():
            c[C] = c[C]+c[B]
        else:
            c[C] = c[B]
        c.pop(B)
    else:
        print(S)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for key in A:
    d[key] += 1
d[sum] = sum(A)

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

Submission status: Accepted

Solution code:
n=int(input())
l = list(map(int,input().split()))
q=int(input())
l1 = [list(map(int,input().split())) for _ in range(q)] #複数行複数入力を多重リストに
d={}
ans=0
for i in l:
    if  i in d:
        d[i]+=1
        ans+=i
    else:
        d[i]=1
        ans+=i
for i in l1:
    if i[0] not in d:
      print(ans)
    elif i[0] in d:
      ans+=i[1]*d[i[0]]-i[0]*d[i[0]]
      if i[1] in d:
        d[i[1]]+=d[i[0]]
      else:
        d[i[1]]=d[i[0]]
      d[i[0]]=0
      print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
counter = collections.Counter(A)
Asum = sum(A)
ans = list()
for i in range(Q):
    B,C = map(int,input().split())
    if B in counter:
        num = counter.pop(B)
        Asum = Asum + (C-B)*num
        counter[C] = counter[C]+num
    ans.append(Asum)
for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(A)
# print(c)

sum_a = sum(A)

for i in range(Q):
	b_num = c[B[i]]
	diff = (C[i]-B[i]) * b_num
	c[C[i]] = c[B[i]] + c[C[i]]
	c[B[i]] = 0
	sum_a = sum_a + diff
	print(sum_a)

Submission status: Accepted

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

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

for i in range(N):
    count_list[arr[i]] +=1

ans = sum(arr)

for i in que:
    keep = count_list[i[0]]
    c_ans = ans+keep*(i[1]-i[0])
    print(c_ans)
    ans =c_ans
    if count_list[i[0]] == 0:
        continue
    if count_list[i[0]] != 0:
        count_list[i[1]] += count_list[i[0]]
        count_list[i[0]] = 0

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = list(map(int, input().split(' ')))
    counter = Counter(A)
    Q = int(input())
    queries = [list(map(int, input().split(' '))) for _ in range(Q)]
    ans = [0 for _ in range(Q)]
    s = sum(A)
    for q in range(Q):
        B, C = queries[q]
        if counter[B] != 0:
            cnt = counter[B]
            counter[C] += cnt
            counter[B] = 0
            s += (C - B) * cnt
        ans[q] = s
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections


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

s = 0
for k, v in cnt.items():
    s += int(k) * v
for i in range(Q):
    BC = list(map(int, input().split()))

    if BC[0] in cnt:
        if BC[1] in cnt:
            cnt[BC[1]] += cnt[BC[0]]
            s += int(BC[1]) * cnt[BC[0]]
            s -= int(BC[0]) * cnt[BC[0]]
            del cnt[BC[0]]
        else:
            cnt[BC[1]] = cnt[BC[0]]
            s += int(BC[1]) * cnt[BC[0]]
            s -= int(BC[0]) * cnt[BC[0]]
            del cnt[BC[0]]
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
AA = {}
t = 0
for a in A:
	t += a
	if a in AA:
		AA[a] += 1
	else:
		AA[a] = 1

Q = int(input())
ans = []
for i in range(Q):
	b, c = list(map(int, input().split()))
	if b in AA:
		if c not in AA:
			AA[c] = 0
		AA[c] += AA[b]
		t += (c - b) * AA[b]
		ans += [t]
		del AA[b]
	else:
		ans += [t]
[print(a) for a in ans]

Submission status: Accepted

Solution code:
from collections import defaultdict
dpa = defaultdict(lambda: 0)
n = int(input())
a = list(map(int, input().split()))
q = int(input())

sum = 0
for i in range(n):
	dpa[a[i]]+=1
	sum+=a[i]

for j in range(q):
	bc = list(map(int, input().split()))
	b = bc[0]
	c = bc[1]
	if(dpa[b] != 0):
		sum = sum+(c-b)*dpa[b]
		print(sum)
		dpa[c] += dpa[b]
		dpa[b] = 0
		#print(dpa)
	else:
		print(sum)

Submission status: Accepted

Solution code:
import collections

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

answer=sum(a)

b=collections.Counter(a)
    
for i in range(Q):    
    num=b[l[i][0]]
    variance=l[i][1]-l[i][0]
    answer+=variance*num
    print(answer)
    b[l[i][0]]=0
    b[l[i][1]]+=num

Submission status: Accepted

Solution code:
def resolve():
    n = int(input())
    a = list(map(int, input().split()))
    total = 0
    count = [0 for _ in range(10**5)]
    for i in range(n):
        count[a[i] - 1] += 1
        total += a[i]

    q = int(input())
    for _ in range(q):
        b, c = list(map(int, input().split()))
        count_b = count[b - 1]
        count[b - 1] = 0
        count[c - 1] += count_b

        total -= count_b * (b - c)
        print(total)


if 'unittest' not in globals():
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)
for a in A:
  D[a] += 1
Q = int(input())
B = []
C = []
for _ in range(Q):
  l = list(map(int, input().split()))
  B.append(l[0])
  C.append(l[1])

ans = sum(A)
for i in range(Q):
  k = D[B[i]]
  D[B[i]] = 0
  D[C[i]] += k
  ans = ans - (B[i]*k) + (C[i]*k)
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
s = Counter(A)
t=[0]*(10**5+1)
for i in range(10**5+1):
    t[i] = s[i]*i

sumnum=sum(t)
for i in range(Q):
    B, C = map(int, input().split())
    num = t[B]//(B)
    t[B] = 0
    t[C] += num*(C)
    sumnum=sumnum-num*B+num*C
    print(sumnum)

Submission status: Accepted

Solution code:
from collections import defaultdict

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


dict_n = defaultdict(lambda:0)

for i in alist:
    dict_n[i] += 1

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

sum = sum(alist)
for i in range(q):
    
    b = bclist[i][0]
    c = bclist[i][1]

    sum += dict_n[b]*c - dict_n[b]*b
    dict_n[c] += dict_n[b]
    del(dict_n[b])

    print(sum)

Submission status: Accepted

Solution code:
import sys

import math
import itertools

n=int(input())
a=list(map(int,input().split()))
q=int(input())
all=0
li=[0]*10**5
for i in a:
    all+=i
    li[i-1]+=1
ans=[]*q

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = {}
for x in a:
  try:
    if b[x] != -1:
      b[x] += 1
  except:
    b[x] = 1
q = int(input())
ans = sum(a)
for _ in range(q):
  x,y = map(int,input().split())
  try:
    if b[x] != -1:
      bx = b[x]
      b[x] = 0
  except:
    print(ans)
    continue
  try:
    if b[y] != -1:
      b[y] += bx
  except:
    b[y] = bx
  ans += bx * (y-x)
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())

L = list(map(int,input().split()))
sum_all = sum(L)
L = Counter(L)
#print(L)
q = int(input())
sum1 = sum_all
for i in range(q):
    
    a,b = map(int,input().split())
    #print(L)
    if a not in L:
        L[a] = 0
    else:
        L[b] +=L[a] 
    #print(L)
    sum1 = sum1 + b*L[a] - a*L[a]
    L[a] =0
    
    #print(L)
    print(sum1)

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)]
x = [0]*10**5
for i in a:
    x[i-1] += 1
ans = sum(a)
for i in range(q):
    b = bc[i][0]
    c = bc[i][1]
    x[c-1] += x[b-1]
    cnt = x[b-1]
    dif = c - b
    ans += dif * cnt
    x[b-1] = 0
    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):
    tmpb,tmpc = map(int,input().split())
    b.append(tmpb)
    c.append(tmpc)

dic = collections.Counter(a)
val = 0
for key, value in dic.items():
    val +=key * value
for i in range(q):
    tmp = 0
    if b[i] in dic:
        if c[i] not in dic:
            dic[c[i]] = 0
        tmp = (c[i] - b[i]) * dic[b[i]]
        dic[c[i]] += dic[b[i]]
        dic[b[i]] = 0
        val = val + tmp
    print(val)

Submission status: Accepted

Solution code:
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


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

    cnt = [0 for i in range(10**5)]
    tot = sum(A)

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

    for i in range(Q):
        temp = BC[i]
        tot += cnt[temp[0]-1] * (temp[1] - temp[0])
        cnt[temp[1]-1] += cnt[temp[0]-1]
        cnt[temp[0]-1] = 0
        print(tot)



main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
A.sort()
Adict={}
q=int(input())
B=[]
C=[]
for i in range(q):
    b,c=map(int,input().split())
    B.append(b)
    C.append(c)

S=[]

last=0
for a in A:
    if last!=a:
        Adict[a]=1
    else:
        Adict[a]+=1
    last=a

sum=0
for a in Adict:
    sum+=Adict[a]*a


for index ,b in enumerate(B):
    if b in Adict:
        c=C[index]
        sum=sum-b*Adict[b]+c*Adict[b]
        if c in Adict:
            Adict[c]+=Adict[b]
        else:
            Adict[c]=Adict[b]
        del Adict[b]
        S.append(sum)
    else:
        S.append(sum)

for s in S:
    print(s)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
a_sum = sum(a)
ac = collections.Counter(a)
q = int(input())
ans = []
for i in range(q):
    b, c = map(int, input().split())
    b_num = ac[b]
    before = b * b_num
    after = c * (b_num)
    a_sum = a_sum - before + after
    ans.append(a_sum)

    tmp = ac[b]
    del ac[b]
    ac[c]+= tmp

[print(total) for total in ans]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations, accumulate, product, combinations_with_replacement
import sys
import bisect
import string
import math
import time


def I(): return int(input())
def S(): return input()
def MI(): return map(int, input().split())
def MS(): return map(str, input().split())
def LI(): return [int(i) for i in input().split()]
def LI_(): return [int(i)-1 for i in input().split()]
def StoI(): return [ord(i)-97 for i in input()]
def ItoS(nn): return chr(nn+97)
def input(): return sys.stdin.readline().rstrip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def print_matrix(mat):
    for i in range(len(mat)):
        print(*['IINF' if v == IINF else "{:0=4}".format(v) for v in mat[i]])


yn = {False: 'No', True: 'Yes'}
YN = {False: 'NO', True: 'YES'}
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)
nums = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10']
show_flg = False
# show_flg = True


def main():
    N = I()
    A = LI()
    Q = I()
    B = [0] * Q
    C = [0] * Q
    cnt = defaultdict(int)

    for i in range(Q):
        B[i], C[i] = MI()


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

    ans = sum(A)

    for i in range(Q):
        b_cnt = cnt[B[i]]
        c_cnt = cnt[C[i]]

        # print(ans, b_cnt * B[i])

        ans -= b_cnt * B[i]
        ans += b_cnt * C[i]

        print(ans)

        cnt[B[i]] = 0
        cnt[C[i]] += b_cnt




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [list(map(int, input().split())) for _ in range(q)]

s = sum(a)
a = collections.Counter(a)

for b, c in query:
    s = s + (c - b) * a[b]
    a[b], a[c] = 0, a[c] + a[b]
    print(s)

Submission status: Accepted

Solution code:
import sys
import  math
from heapq import *
import fractions
import bisect
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N=int(input())
A=nl()
ans_l=[0]*(10**5+5)
for i in A:
    ans_l[i]+=1

a_sum=0
for i in range(len(ans_l)):
    a_sum+=(i*ans_l[i])

Q=int(input())
for i in range(Q):
    B,C=nm()
    ans_l[C]+=ans_l[B]
    a_sum-=ans_l[B]*B
    a_sum+=ans_l[B]*C
    ans_l[B]=0
    print(a_sum)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(v) for v in input().split()]
q=int(input())
d=dict()
s=0
for j in range(n):
    if a[j] in d:
        d[a[j]]=d[a[j]]+1
    else:
        d[a[j]]=1
    s=s+a[j]
for j in range(q):
    b,c=map(int,input().split())
    if b in d:
        s=s-(d[b]*b)+d[b]*c
        if c in d:
            d[c]=d[c]+d[b]
        else:
            d[c]=d[b]
        del d[b]
    print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

num_of_numbers = int(input())
numbers = list(map(int, input().split()))
num_of_operation = int(input())

# intで初期化するため0が返る
cnt = collections.defaultdict(int)
# numbersに含まれる各数字の出現回数を保持
for i in numbers:
    cnt[i] += 1

# 初期状態の和を算出
ans = sum(numbers)

for i in range(num_of_operation):
    B, C = map(int, input().split())

    # 置換対象の数字が存在する場合
    if B in cnt:
        tmpB = cnt[B]
        tmpC = cnt[C]
        ans = ans - (B * tmpB) + (C * tmpB)

        cnt[C] = tmpC + tmpB
        cnt.pop(B)

    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
Ad = {a:0 for a in A}
S = 0
for a in A:
    Ad[a] += 1
    S += a
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(Q):
    if B[i] in Ad:
        if C[i] in Ad:
            Ad[C[i]] += Ad[B[i]]
        else:
            Ad[C[i]] = Ad[B[i]]
        S += (C[i]-B[i]) * Ad[B[i]]
        Ad[B[i]] = 0

    print(S)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
bc_list = []
for _ in range(q):
    bc_list.append(list(map(int, input().split())))

sum_num = sum(a_list)
counter = Counter(a_list)

for i, (b, c) in enumerate(bc_list):
    sum_num = sum_num + ((c - b) * counter[b])
    counter[c] = counter[c] + counter[b]
    counter[b] = 0
    print(sum_num)

Submission status: Accepted

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

Submission status: Accepted

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

#最初に全探索で位置をインデックスに登録する
DP=[0]*(10**5+1)
for i in A:
    DP[i]+=1#
ans=sum(A)
for i in BC:
    target=i[0]
    nex=i[1]
    num=DP[target]
    DP[target]=0
    DP[nex]=DP[nex]+num
    ans=ans+num*nex-num*target
    print(ans)

Submission status: Accepted

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


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


sumA = sum(alist)
adict = Counter(alist)

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

    if b not in adict:
        print(sumA)
        continue

    bnum = adict.pop(b)
    if c in adict:
        adict[c] += bnum
    else:
        adict[c] = bnum

    sumA -= bnum * (b - c)
    print(sumA)

Submission status: Accepted

Solution code:
# /usr/bin/python3
# -*- coding: utf-8 -*-
from queue import Queue
from queue import LifoQueue as Stack
from math import sqrt, floor, ceil, log2, log10, pi
from fractions import gcd
from itertools import permutations, combinations
from operator import itemgetter
from functools import cmp_to_key


INF=1001001001
__MOD__=(10**9)+7
yn = 'YNeos'
judge = False
cnt = 0
ans = None


def lcm(a, b):
    return (a*b) // gcd(a,b)

def intinput():
    return int(input())

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

def lineinputs(func=intinput):
    datas = []
    while True:
        try:
            datas.append(func())
        except EOFError:
            break
    return datas

class ModInt():
    def __init__(self, x):
        self.__x = (x % __MOD__)
    def __add__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x + other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x + other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __radd__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x + self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x + self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __sub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x - other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x - other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rsub__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x - self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x - self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __mul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rmul__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__x)%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__x)%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __truediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((self.__x * other.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((self.__x * other.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")
    def __rtruediv__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__((other.__x * self.__modinv())%__MOD__))
        elif type(other) == ModInt:
            return self.__class__((other.__x * self.__modinv())%__MOD__)
        else:
            raise Exception("Not Int or Not ModInt")

    def __pow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(self.__x, other.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(self.__x, other.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")
    def __rpow__(self, other):
        if type(other) == int:
            other = self.__class__(other)
            return int(self.__class__(pow(other.__x, self.__x, __MOD__)))
        elif type(other) == ModInt:
            return self.__class__(pow(other.__x, self.__x, __MOD__))
        else:
            raise Exception("Not Int or Not ModInt")

    def __modinv(self, m=__MOD__):
        a = self.__x
        if a == 0:
            raise ZeroDivisionError()
        if gcd(a, m) != 1:
            raise Exception("%sの逆数は求まりません。" % a)
        b, u, v = m, 1, 0
        while b != 0:
            t = a//b;
            a -= t*b
            a, b = b, a
            u -= t * v
            u, v = v, u
        u %= m
        if u < 0:
            u += m
        return u
    def __int__(self):
        return self.__x
    def __str__(self):
        return str(self.__x)



if __name__ == '__main__':
    N = intinput()
    a_list = list(mulinputs())
    Q = intinput()
    bc_list = []
    for _ in range(Q):
        B, C = mulinputs()
        bc_list.append((B,C))
    t, bucket = 0, [0] * ((10**5) + 1)
    for a in a_list:
        t += a
        bucket[a] += 1
    for b, c in bc_list:
        d = c - b
        if bucket[b] != 0:
            n = bucket[b]
            t += n*d
            bucket[b] -= n
            bucket[c] += n
            # print(f"t: {t}, b: {b}, c: {c}, d: {c-b}, bucket[{b}]: {bucket[b]}, bucket[{b}]: {bucket[b]}, bucket[{c}]: {bucket[c]}")
        print(t)

Submission status: Accepted

Solution code:
n = int(input())
list_A = list(map(int, input().split()))
d = {}
for i in range(1, pow(10, 6)):
    d[i] = 0

ans = sum(list_A)
for i in list_A:
    d[i] += 1

m = int(input())
list_ANS = []
list_AB = []

for _ in range(m):
    a, b = map(int, input().split())
    list_AB.append([a, b])

for a, b in list_AB:
    ans += (b-a)*d[a]
    list_ANS.append(ans)
    d[b] += d[a]
    d[a] = 0


for i in range(m):
    print(list_ANS[i])

Submission status: Accepted

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

for i in range(Q):
  L, R = map(int,(input().split()))
  sa=(R-L)*col[L]
  col[R]+=copy.copy(col[L])
  col[L]=0
  ans= ans+sa
  print(ans)

Submission status: Accepted

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

ans = sum(a)
A = Counter(a).most_common()
d = [0] * (10**5+10)
for i in range(len(A)):
    d[A[i][0]] = A[i][1]

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

for i in range(q):
    d[C[i]] += d[B[i]]
    cnt = d[B[i]]
    ans += (C[i]-B[i])*cnt
    print(ans)
    d[B[i]] = 0

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import numpy as np

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

npdata = np.arange(10**5+1)

kosuu=np.zeros(10**5+1)
kosuumoto=kosuu
for i in range(N):
    a=A[i]
    kosuu[a]+=1
SUM=sum(A)

BC_list=[]

for i in range (Q):
    bc=list(map(int,input().split()))
    BC_list.append(bc)
S=SUM
for i in range(Q):
    b=BC_list[i][0]
    c=BC_list[i][1]
    minus=b*kosuu[b]
    plus=c*kosuu[b]
    kosuu[c]=kosuu[c]+kosuu[b]
    kosuu[b]=0
    S=S-minus+plus
    print(int(S))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    from builtins import int, map, list, print, len
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(10 ** 6)

    input = (lambda: (sys.stdin.readline()).rstrip())
    input_list = (lambda: input().split())
    input_number = (lambda: int(input()))
    input_number_list = (lambda: list(map(int, input_list())))

    N = input_number()
    A_ls = input_number_list()
    d = defaultdict(lambda: 0)
    for i in range(len(A_ls)):
        d[A_ls[i]] += 1
    Q = input_number()

    total = sum(A_ls)

    for i in range(Q):
        B, C = input_number_list()
        cnt = d[B]
        total -= cnt * B
        total += cnt * C
        d[C] += cnt
        d[B] = 0
        print(total)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=[int(i) for i in input().split()]

c = collections.Counter(a)
suma=sum(a)
q=int(input())
for i in range(q):
    x,y=map(int,input().split())
    print(suma+c[x]*(y-x))
    suma+=c[x]*(y-x)
    c[y]+=c[x]
    c[x]=0

Submission status: Accepted

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

d = Counter(A)
total = sum(A)

for _ in range(Q):
    b, c = [int(s) for s in input().split()]
    if d[b]:
        total += (c - b) * d[b]
        d[c] = d[b] + (d[c] if d[c] else 0)
        d[b] = 0
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter
from decimal import *

N = int(input())
dp = [0]*(10**5+1)
A = []
for n in input().split():
    n = int(n)
    dp[n] += 1
    A.append(n)
ans = sum(A)
Q = int(input())
for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    diff = dp[B] * (C-B)
    ans += diff
    print(ans)
    dp[C] += dp[B]
    dp[B] = 0

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
import re
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor
sys.setrecursionlimit(1000000)


def main():
    #N, M = map(int, input().split())
    #N, K = map(int, input().split())
    #ps = list(map(int, input().split()))

    N = int(input())
    nums = defaultdict(int)
    As = list(map(int, input().split()))
    for A in As:
        nums[A] += 1

    total = sum([key * value for key, value in nums.items()])

    Q = int(input())
    for i in range(Q):
        B, C = map(int, input().split())
        if B in nums:
            nums[C] += nums[B]
            diff = (C - B) * nums[B]
            del nums[B]
            total += diff
        print(total)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
q = int(input())
am = sum(a)
a = Counter(a).most_common()
defs = defaultdict(int)
for i in range(len(a)):
    defs[a[i][0]] = a[i][1]

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