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

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

for bc in b_to_c:
    b = bc[0]
    c = bc[1]
    sum -= (b * memo[b])
    sum += (c * memo[b])
    memo[c] += memo[b]
    memo[b] = 0
    print(sum)

Submission status: Accepted

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

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):
    input_q = list(map(int, input().split()))
    B.append(input_q[0])
    C.append(input_q[1])
    
A_sum = sum(A)
CONST_MAX = 100001
count_list = [0] * CONST_MAX

c = collections.Counter(A)
for k, v in c.items():
    # print(k, v)
    count_list[k] = v


for i in range(Q):
    count_list[C[i]] += count_list[B[i]]
    A_sum += (C[i] - B[i]) * count_list[B[i]]
    count_list[B[i]] = 0
    # print(count_list)

    print(A_sum)

Submission status: Accepted

Solution code:
import sys
import copy
from collections import deque
import collections
stdin = sys.stdin

mod = 10**9+7

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

a = na()
suma = sum(a)
collection = dict(collections.Counter(a))


q = ni()
res = []
for _ in range(q):
    b, c = na()
    if b in collection:
        bnum = collection[b]
        del collection[b]
    else:
        bnum = 0
    suma -= b*bnum
    suma += c*bnum
    if c in collection:
        collection[c] += bnum
    else:
        collection[c] = bnum
    res.append(suma)

for i in res:
    print(i)

Submission status: Accepted

Solution code:
n = int(input())
b_list = list(map(int, input().split()))
q = int(input())
a_list=[0]*100000
for i in b_list :
  a_list[i-1]+=1
count=sum(b_list)
for i in range(q):

  b, c = map(int, input().split())
  count+=(c-b)*a_list[b-1]
  print(count)

  a_list[c - 1] +=a_list[b-1]
  a_list[b - 1] = 0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#import math
#import numpy as np
#import torch
#import torch.nn as nn
#import matplotlib.pyplot as plt
#from decimal import Decimal
#import itertools
import collections

N=int(input())
#N,K = map(int,input().split())
#B,W = map(int,input().split())
#T=int(input())
A = list(map(int,input().split()))
#S=str(input())
#A=[p for p in range(2*10**5)]
Q=int(input())
c=collections.Counter(A)
s=sum(A)
for i in range(Q):
    #print(A)
    B,C = map(int,input().split())
    if c[B]:
        s += (C-B)*c[B]
        c[C] += c[B]
        c[B] = 0

    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
li = [0]*(10**5+10)
 
for i in A:#出現する個数の管理
    li[i] += 1
 
ans = sum(A)#
 
for i in range(Q):
    B,C = map(int,input().split())
    ans += li[B]*C - li[B]*B
    print(ans)
    li[C] += li[B]#個数を追加する
    li[B] = 0#置換されたAnは必ず0となる

Submission status: Accepted

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

for i in A:#出現する個数の管理
    li[i] += 1

ans = sum(A)#

for i in range(Q):
    B,C = map(int,input().split())
    ans += li[B]*C - li[B]*B
    print(ans)
    li[C] += li[B]#個数を追加する
    li[B] = 0#置換されたAnは必ず0となる

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(input().split())
q = int(input())
ansList = [0]*q
d = Counter(A)
Sum = sum(map(int,A))

for i in range(q):
    b,c = input().split()
    Sum -= (int(b)-int(c))*d[b]
    if b in d:
        if c in d:
            d[c] += d.pop(b)
        else:
            d[c] = d.pop(b)
    ansList[i]  +=  Sum

[print(ans) for ans in ansList]

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self,n):
        self.size=n
        self.tree=[0]*-~n
    def sum(self,i):
        s=0
        while i:
            s+=self.tree[i]
            i-=i&-i
        return s
    def add(self,i,x):
        while i<=self.size:
            self.tree[i]+=x
            i+=i&-i
def main():
    n=int(input())
    bit=BIT(10**5)
    for a in map(int,input().split()):
        bit.add(a,a)
    for _ in range(int(input())):
        b,c=map(int,input().split())
        t=bit.sum(b)-bit.sum(b-1)
        bit.add(b,-t)
        bit.add(c,t//b*c)
        print(bit.sum(10**5))
main()

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
su = sum(arr)
lst = [0]*100001
q = int(input())
for i in arr:
    lst[i] += 1
for _ in range(q):
    b, c = map(int, input().split())
    su += (c - b) * lst[b]
    print(su)
    lst[c] += lst[b]
    lst[b] = 0

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)

S = []
 
#1 iterlation
S.append(sum(A))
for i in range(N):
    num[A[i]]+=1

    
for j in range(Q):
    if num[BC[j][0]] != 0:
        #Bに当たる交換するものがある時
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1] + (C - B)*num[B] )
        #S[-1]で合計の一番最新のもの
        dammy = num[B]
        num[B] = 0
        num[C] += dammy
 
    else:
        B = BC[j][0]
        C = BC[j][1]
        S.append(S[-1])

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

Submission status: Accepted

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

    l = {i:0 for i in range(1,100001)}
    for num in A:
        l[num] += 1

    s = sum(A)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
Q = int(input().strip())
BC_list = [list(map(int, input().rstrip().split())) for i in range(Q)]
#-----

A_dic = {}
sum_A = 0

for num in A_list:
    A_dic.setdefault(num, 0)
    A_dic[num] += 1

    sum_A += num


for b,c in BC_list:
    if b in A_dic:
    
        if c in A_dic:
            A_dic[c] += A_dic[b]
            
        else:
            A_dic[c] = A_dic[b]
    
        sum_A += (c-b) * A_dic[b]
        del A_dic[b]
    
    print(sum_A)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    s = 0
    l = {i:0 for i in range(1,100001)}

    s = sum(A)
    for num in A:
        l[num] += 1



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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    s = 0
    l = {i:0 for i in range(1,100001)}

    A.sort()
    for num in A:
        l[num] += 1
        s += num



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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

cnt = [0] * 100005 

for i in range(n):
    cnt[a[i]] += 1
    
tot = 0
for j in range(len(cnt)):
    tot += j * cnt[j]

# print(tot)

for k in range(q):
    b = bc[k][0]
    c = bc[k][1]
    tot -= b*cnt[b]
    tot -= c*cnt[c]
    cnt[c] += cnt[b]
    cnt[b] = 0
    tot += b*cnt[b]
    tot += c*cnt[c]
    print(tot)

Submission status: Accepted

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

s = sum(a)

# 辞書型で度数を持つ
hist = {}
for i in range(n):
    if a[i] in hist:
        hist[a[i]] += 1
    else:
        hist[a[i]] = 1
# print(hist)

for i in range(q):
    diff = c[i] - b[i]
    if b[i] in hist:
        s += hist[b[i]]*diff
        print(s)
        if c[i] in hist:
            hist[c[i]] += hist[b[i]]
            del hist[b[i]]
        else:
            hist[c[i]] = hist[b[i]]
            del hist[b[i]]
    else:
        print(s)
    # print(hist)

Submission status: Accepted

Solution code:
n = int(input())+1
a = list(map(int, input().split()))
cnt = []
for i in range(100005):
    cnt.append(0)
sum = 0

# a.count(i)を使うとTLE
# count()がO(N)のためfor内で使用するとO(N2)になる？
for i in a:
    cnt[i] += 1
for i in range(100005):
    sum += i * cnt[i]

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

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    s = 0
    n = [0] * (10**5+1)
    for a in map(int, input().split()):
        s += a
        n[a] += 1
    q = int(input())
    for _ in range(q):
        b, c = map(int, input().split())
        s += (c - b) * n[b]
        print(s)
        n[c] += n[b]
        n[b] = 0


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    s = 0
    n = [0 for _ in range(100000+1)]
    for a in map(int, input().split()):
        s += a
        n[a] += 1
    q = int(input())
    for _ in range(q):
        b, c = map(int, input().split())
        s += (c - b) * n[b]
        print(s)
        n[c] += n[b]
        n[b] = 0


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())+1
a = list(map(int, input().split()))
cnt = []
for i in range(100005):
    cnt.append(0)
sum = 0

for i in a:
    cnt[i] += 1
for i in range(100005):
    sum += i * cnt[i]

q = int(input())

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

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    a = list(map(int, input().split()))
    s = sum(a)
    q = int(input())
    n = [0 for _ in range(100000+1)]
    for i in a:
        n[i] += 1
    for _ in range(q):
        b, c = map(int, input().split())
        s += (c - b) * n[b]
        print(s)
        n[c] += n[b]
        n[b] = 0


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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: 
    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)
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
suma=sum(a)
q=int(input())
b=[]
c=[]
for i in range(q):
  b_,c_=map(int,input().split())
  b.append(b_)
  c.append(c_)

counter=[0]*(10**5+1)
for i in a:
  counter[i]+=1
new_sum=suma
for i in range(q):
  new_sum=new_sum-b[i]*counter[b[i]]+c[i]*counter[b[i]]
  
  counter[c[i]]+=counter[b[i]]
  counter[b[i]]=0
  print(new_sum)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

target_list = list(map(int, input().split()))
check = Counter(target_list)
result = sum(target_list)


for index in range(int(input())):
    B, C = map(int, input().split())
    if B in check:
        result = result + (check[B]) * (C - B)
        if C in check:
            check[C] = check[C] + check[B]
        else:
            check[C] = check[B]
        check[B] = 0
    print(result)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
q = int(input())
cnt_A = dict(Counter(A))
ans = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b in cnt_A and cnt_A[b] > 0:
        count = cnt_A[b]
        cnt_A[b] = 0
        if c not in cnt_A:
            cnt_A[c] = count
        else:
            cnt_A[c] += count
        ans += ((c - b) * count)
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# D

dct = {i: 0 for i in range(1, 10**5 + 1)}
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
ans = 0
for i in A:
    dct[i] += 1
    ans += i
for i in range(Q):
    b, c = map(int, input().split())
    if (dct[b] == 0):
        print(ans)
        continue
    else:
        ans -= b * dct[b]
        ans += c * dct[b]
        dct[c] += dct[b]
        dct[b] = 0
        print(ans)

Submission status: Accepted

Solution code:
import collections
#入力
N = int(input())
n = 100001
Alist = list(map(int,input().split()))
Q = int(input())
Blist = []
Clist = []
for i in range(Q):
  B, C = map(int,input().split())
  Blist.append(B)
  Clist.append(C)

Adic = dict(collections.Counter(Alist))
numlist = [0]*n

for j in range(n):
  if j in Adic:
    numlist[j] = Adic[j]
sum = sum(Alist)
for k in range(Q):
  sum += (Clist[k]-Blist[k])*numlist[Blist[k]]
  numlist[Clist[k]] += numlist[Blist[k]] 
  numlist[Blist[k]] = 0

  print(sum)

Submission status: Accepted

Solution code:
import collections
import copy
n = int(input())
a = list(map(int,input().split()))
suma = sum(a)
numcount = [0] * ((10 ** 5) + 1)
for i in range(n):
         numcount[a[i]] += 1
q = int(input())
for i in range(q):
         b,c = map(int,input().split())
         if numcount[b] != 0:
                  tmpb = numcount[b]
                  numcount[c] += numcount[b]
                  numcount[b] = 0
                  suma += tmpb*(c - b)
         print(suma)

Submission status: Accepted

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

Submission status: Accepted

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

if __name__ == '__main__':
  n=int(input())
  A_str=input().strip("\n")
  A=A_str.split()
  q=int(input())

  C={}
  for a in A:
    if a in C:
      C[a]+=1
    else:
      C[a]=1
  
  def rep(b,c):
    if c in C:
      C[c]+=C[b]
    else:
      C[c]=C[b] 
    C[b]=0
    #print(b,c,C)

  Ans=[]
  ans=''
  b,c=input().strip("\n").split()
  #tmp=eval(A_str.replace(b,c).replace(" ","+"))
  tmp=0
  hoge=map(int,A)
  for a in hoge:
    if str(a)==b:
      tmp+=int(c)
    else:
      tmp+=a
  #ans+=str(tmp)
  #ans+="\n"
  Ans.append(tmp)
  if b in C:
    rep(b,c)
  for i in range(1,q-1):
    b,c=input().strip("\n").split()
    if b in C:
      tmp+=(int(c)-int(b))*C[b]
      rep(b,c)
    #ans+=str(tmp)+"\n"
    Ans.append(tmp)
  b,c=input().strip("\n").split()
  if b in C:
    tmp+=(int(c)-int(b))*C[b]
  #ans+=str(tmp)
  Ans.append(tmp)
  #print(ans)
  for ans in Ans:
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    
    table = [0] * 100001
    
    c = 0
    s = 0
    
    for i in A:
        table[i] += 1
        s += i
    
    for i in range(Q):
        B, C = map(int, input().split())
        c = table[B]
        s += (C - B) * c
        table[C] += table[B]
        table[B] = 0
        print(s)

main()

Submission status: Accepted

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

ans = sum(a)
s = Counter(a)
for i in range(q):
    bi,ci = map(int, input().split())
    b.append(bi)
    c.append(ci)
for i in range(q):
    ans += s[b[i]] * (c[i]-b[i])
    s[c[i]] += s[b[i]]
    s[b[i]] = 0
    print(ans)

Submission status: Accepted

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

for i in range(q):
  dif = b[i][1]-b[i][0]
  #print(dif)
  sum_a += dif*num[b[i][0]]
  num[b[i][1]] += num[b[i][0]]
  num[b[i][0]] = 0
  print(sum_a)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

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

N = int(readline())
A = tuple(map(int, readline().split()))
Q = int(readline())
BC = map(int, read().split())

d = Counter(A)

sub_s = sum(A)

for b, c in zip(BC, BC):
    sub_s += d[b] * (c - b)
    d[c] += d[b]
    d[b] = 0

    print(sub_s)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
dic = {}
suma = sum(a)

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

for j in bc:
    dif = j[1] - j[0]
    if j[0] in dic:
        suma += dif * dic[j[0]]
    else:
        print(suma)
        continue
    if j[1] in dic:
        dic[j[1]] += dic.pop(j[0])
    else:
        dic[j[1]] = dic.pop(j[0])
    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 _ in range(q)]
s = 0
for g in range(len(a)):
    s += a[g]
e = [0] * 100001
for i in a:
    e[i] += 1
for j in range(q):
    s += (bc[j][1] - bc[j][0]) * e[bc[j][0]]
    e[bc[j][1]] += e[bc[j][0]]
    e[bc[j][0]] = 0
    print(s)

Submission status: Accepted

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

ans = sum(a)
for _ in range(Q):
    B, C = map(int, input().split())
    if B in A.keys():
        if C in A.keys():
            A[C] += A[B]
        else:
            A[C] = A[B]
        ans += (C-B)*A[B]
        A[B] = 0
    print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
b=[0]*q
c=[0]*q
s=[0]*(q+1)
for i in range(q):
	b[i],c[i]=map(int,input().split())
f={}
for i in range(n):
	f.setdefault(a[i],0)
for i in range(n):
	f[a[i]]+=1
for g,h in f.items():
	#print(len(h)*g)
	s[0]=s[0]+h*g
#print(f)
for i in range(1,q+1):
	if b[i-1] in f:
		if c[i-1] in f:
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]=s[i]+f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
		else:
			f.setdefault(c[i-1],0)
			f[c[i-1]]=f[c[i-1]]+f[b[i-1]]
			s[i]=s[i-1]-f[b[i-1]]*b[i-1]
			#print(s[i])
			
			s[i]+=f[b[i-1]]*c[i-1]
			f.pop(b[i-1])
	#print(f)
	#for g,h in f.items():
		#print(len(h)*g)
		#s[i]=s[i]+len(h)*g
	else:
		s[i]=s[i-1]
	print(s[i])

Submission status: Accepted

Solution code:
from collections import defaultdict

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

Submission status: Accepted

Solution code:
from collections import Counter

import sys

readline = sys.stdin.buffer.readline

N = int(readline())
A = tuple(map(int, readline().split()))

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

d = Counter(A)

sub_s = sum(A)

for b, c in BC:
    sub_s += d[b] * (c - b)
    d[c] += d[b]
    d[b] = 0

    print(sub_s)

Submission status: Accepted

Solution code:

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

Submission status: Accepted

Solution code:
from collections import Counter

import sys

readline = sys.stdin.buffer.readline

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

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

d = Counter(A)

sub_s = sum(A)

for b, c in BC:
    sub_s += d[b] * (c - b)
    d[c] += d[b]
    d[b] = 0

    print(sub_s)

Submission status: Accepted

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

for i in a:
    data[i] += 1
res = sum(a)

for j in range(q):
    b, c = map(int, input().split())
    res += (c - b) * data[b]
    data[c] += data[b]
    data[b] = 0
    print(res)

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

ans = sum(A)

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

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

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
arr = list(map(int, input().split()))
dct = dict(Counter(arr))
sm = sum(arr)

q = int(input())
for _ in range(1, q+1):
    b, c = map(int, input().split())
    if b in dct:
        n = dct[b]
        dct[b]=0
        if c in dct:
            dct[c]+=n
        else:
            dct[c]=n
        sm = sm + (c-b)*n
    else:
        pass

    
    print(sm)

Submission status: Accepted

Solution code:
import collections

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

c=collections.Counter(A)
S = sum(A)

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def main():
    N = in_n()
    A = list(in_nn())
    Q = in_n()
    t = in_na()
    BC = list(zip(t, t))

    d = defaultdict(int)
    for i in range(N):
        d[A[i]] += 1

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

    for i in range(Q):
        b, c = BC[i]
        s += d[b] * (c - b)
        d[c] += d[b]
        d.pop(b)

        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans = sum(a)
num = collections.Counter(a)

for i in range(q):
    before = bc[i][0]
    after = bc[i][1]
    ans += num[before]*(after-before)
    num[after] += num[before]
    num[before] = 0
    #print(a.count(before))
    #print(num(before))
    print(ans)

Submission status: Accepted

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

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

d = [0] * (10**5 + 7)
for a in A:
    d[a] += 1
sum_a = sum(A)
for j in range(Q):
    before = d[C[j]]
    d[C[j]] += d[B[j]]
    sum_a -= d[B[j]] * B[j]

    sum_a += (d[C[j]] - before) * C[j]
    d[B[j]] = 0
    print(sum_a)

Submission status: Accepted

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

d = {}
t = 0
for i in a:
    if not i in d.keys():
        d[i] = 1
    else:
        d[i] += 1
    t += int(i)

q = int(input())

for _ in range(q):
    b, c = map(str, input().split())
    diff = 0
    if b in d.keys() and c in d.keys():
        diff = (int(c) - int(b)) * d[b]
        d[c] += d[b]
        d.pop(b)
    elif b in d.keys():
        diff = int(c) * d[b] - int(b) * d[b]
        d[c] = d[b]
        d.pop(b)
    t += diff
    print(t)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
A = [0]*1000000

for i in a:
    A[i] += 1
    
ans = sum(a)

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

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)]
 
ans = sum(A)
cnt = collections.Counter(A)
 
dp = [0]*(10**5+1)
 
for i in cnt.items():
    dp[i[0]] = i[1]
 
for i in range(Q):
    ans += (BC[i][1] - BC[i][0]) * dp[BC[i][0]]
    dp[BC[i][1]] += dp[BC[i][0]]
    dp[BC[i][0]] = 0
    print(ans)

Submission status: Accepted

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

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

dict = {}

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

s = sum(a)

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

Submission status: Accepted

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

for _ in range(Q):
    bi, ci = list(map(int, input().split()))
    B.append(bi)
    C.append(ci)

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

sum = sum(A)

for i in range(Q):
    sum += dic.get(B[i], 0) * (C[i] -B[i])
    dic[C[i]] = dic.get(C[i], 0) + dic.get(B[i], 0)
    dic[B[i]] = dic.get(B[i], 0)
    dic[B[i]] = 0
    print(sum)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = map(int, input().split())
Q = int(input())
ops = []
for _ in range(Q):
  b, c = map(int, input().split())
  ops.append((b,c))

cnt = Counter(A)
s = sum(k*v for k, v in cnt.items())
for b, c in ops:
  s -= b * cnt[b]
  s += c * cnt[b]
  cnt[c] += cnt[b]
  cnt[b] = 0
  print(s)

Submission status: Accepted

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

last = sum([v*a[v] for v in a])
for _ in range(q):
  b,c = map(int,input().split())
  last = last - b*a.get(b,0) + c*a.get(b,0)
  a[b],a[c] = 0, a.get(c,0)+a.get(b,0)
  print(last)

Submission status: Accepted

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

cnt = [0] * 100001
s = 0

for x in a:
    cnt[x] += 1
    s += x

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

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
sum = 0
for x in arr:
	sum = sum+x
q = int(input())
newarr = [0]*10**6
for x in arr:
	newarr[x]=newarr[x]+1
for t in range(q):
	b, c = map(int, input().split())
	sum = sum - b*newarr[b]
	sum = sum + c*newarr[b]
	newarr[c] = newarr[c] + newarr[b]
	newarr[b] = 0
	print(sum)

Submission status: Accepted

Solution code:
import collections
N = int(input())
D = [0]*100001
A = list(map(int, input().split()))
a = sum(A)
for j in A:
    D[j] += 1
Q = int(input())
start = sum(A)
for i in range(Q):
    x,y=[int(i) for i in input().split()]
    a += D[x]*(y-x)
    print(a)
    D[y] +=D[x]
    D[x] = 0

Submission status: Accepted

Solution code:
def d_replacing():
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    Queries = [[int(i) for i in input().split()] for j in range(Q)]

    total = sum(A)
    sequence = Counter(A)

    ans = []
    for b, c in Queries:
        total += (c - b) * sequence[b]  # 値を変更
        ans.append(total)
        sequence[c] += sequence[b]  # 要素の個数を更新
        del sequence[b]  # 「個数を 0 とする」でもよい
    return ' '.join(map(str, ans))

print(d_replacing())