Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    d = [0] * 10**5 * 2
    ans = 0
    for a in mis():
        d[a] += 1
        ans += a
    Q=ii()
    for _ in range(Q):
        b, c = mis()
        d[c] += d[b]
        ans -= d[b]*b
        ans += d[b]*c
        d[b] = 0
        print(ans)


main()

Submission status: Accepted

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

cnt = Counter(A)
lst = [0]*(10**5+1)

for i,j in cnt.items():
    lst[i] = j
ans = sum(A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += lst[b]*(c-b)
    lst[c] += lst[b]
    lst[b] = 0
    print(ans)

Submission status: Accepted

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

dic = {}

ans = sum(a)
for i in range(n):
  dic.setdefault(a[i], 0)
  dic[a[i]] += 1

q = int(input())

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

Submission status: Accepted

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

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

suma=sum(a)

for [bk,nx] in query:
    #bkをnxにする
    #つまりbk*
    suma=suma-bk*c[bk]+nx*c[bk]
    print(suma)
    c[nx]+=c[bk]
    c[bk]=0
    #print(c)

Submission status: Accepted

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

n = int(readline())
a = list(map(int,readline().split()))
q = int(readline())
bc = list(map(int,read().split()))

from collections import defaultdict
d = defaultdict(int)

for i in a:
    d[i] += 1

ans = []
si = sum(a)
it = iter(bc)
for b,c in zip(it,it):
    d[c] += d[b]
    si += (c*d[b]) - b*d[b]
    d[b] = 0
    ans.append(si)

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

Submission status: Accepted

Solution code:
A=int(input())
l=list(map(int,input().split()))
list_change=[0]*100001
for i in l:
   list_change[i]+=1
N=int(input())
total=sum(l)
for i in range(N):
   A,B=list(map(int,input().split()))
   X=list_change[A]
   list_change[A]=0
   list_change[B]+=X
   total+=(B-A)*X
   print(total)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
    to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
    print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

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

    def map_int_input():
        return map(int, input())

    MII = map_int_input

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

    def MII_to_index():
        return map(to_index, input())

    def MII_split_to_index():
        return map(to_index, input().split())

    # 入力全てを整数に変換したものの配列を受け取る
    def list_int_inputs():
        return list(map(int, input()))

    LII = list_int_inputs

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

    # 2次元リスト化
    def LII_2D(rows_number):
        return [LII() for _ in range(rows_number)]

    def LII_split_2D(rows_number):
        return [LII_split() for _ in range(rows_number)]

    N = input_int()
    As = LII_split()
    Q = input_int()

    d = dict()
    for i in range(int(1e5)):
        d[i + 1] = 0
    for A in As:
        d[A] += 1

    ans = sum(As)
    for _ in range(Q):
        B, C = MII_split()
        d[C] += d[B]
        ans += (C - B) * d[B]
        d[B] = 0
        print(ans)
        
resolve()

Submission status: Accepted

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

A = dict()
for i in range(n):
    a = aa[i]
    if a not in A.keys():
        A[a] = 1
    else:
        A[a] += 1

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

ans = sum(aa)
for b, c in bc:
    if b in A.keys() and c in A.keys():
        A[c] += A[b]
        ans = ans - b * A[b] + c * A[b]
        A[b] = 0
    elif b in A.keys() and c not in A.keys():
        A[c] = A[b]
        ans = ans - b * A[b] + c * A[b]
        A[b] = 0
    print(ans)

Submission status: Accepted

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

# それぞれの数がいくつあるかを管理

from collections import defaultdict
dic = defaultdict(int)

N = int(readline())
A = list(map(int,readline().split()))
ans = 0
for i in range(len(A)):
  dic[A[i]] += 1
  ans += A[i]

Q = int(readline())

for i in range(Q):
  b,c = map(int,readline().split())
  # bがdic[b]個分減り、cがdic[b]個分増える
  ans += c * dic[b] - b * dic[b]
  print(ans)
  dic[c] += dic[b]
  dic[b] = 0

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Co = Counter(A)
Q = int(input())
BC = [list(map(int, sys.stdin.readline().split())) for i in range(Q)]
ans = sum(A)
for i in range(Q):
    B, C = BC[i]
    ans += ((C - B) * Co[B])
    print(ans)
    Co[C] += Co[B]
    Co[B] = 0

Submission status: Accepted

Solution code:
import numpy as np

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

#rint(BCs)

ansArray = np.zeros(10**5 + 1, dtype = int)
indexArray = np.array(range(10**5+1))

for A in As:
    ansArray[A] += 1

#print(ansArray)
#print(indexArray)
ans = np.dot(ansArray, indexArray)

for BC in BCs:

    ans = ans + (BC[1] - BC[0]) * ansArray[BC[0]]
    print(ans)
    ansArray[BC[1]] += ansArray[BC[0]]
    ansArray[BC[0]] = 0

Submission status: Accepted

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

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

for i in range(len(A)):
    li2[A[i]] += 1

sum1 = sum(A)

for i in range(len(li)):
    sum1 += li2[li[i][0]] * (li[i][1] - li[i][0])
    li2[li[i][1]] += li2[li[i][0]]
    li2[li[i][0]] = 0
    print(sum1)

Submission status: Accepted

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

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:
        sub = b * sequence[b]
        add = c * sequence[b]
        total += add - sub
        ans.append(total)
        sequence[c] += sequence[b]
        sequence[b] = 0
    return '\n'.join(map(str, ans))

print(d_replacing())

Submission status: Accepted

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
sys.setrecursionlimit(10 ** 7)
import bisect
# ----------

INF = float("inf")
MOD = 10 ** 9 + 7
# ----------

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

Q = int(input())

sm = 0
for k, v in D.items():
    sm += k * v


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

Submission status: Accepted

Solution code:

import collections
n = int(raw_input())
nums = map(int,raw_input().split(' '))
q = int(raw_input())
s = sum(nums)
h = collections.Counter(nums)
for _ in range(q):
	ov,nv = map(int, raw_input().split(' '))
	h[nv] += h[ov]
	s += h[ov] * (nv - ov)
	
	h[ov] = 0
	print s

Submission status: Accepted

Solution code:
from collections import Counter

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

count_a = Counter(a)
ans = sum(a)

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

Submission status: Accepted

Solution code:
loop_cnt = 10 ** 5 + 1

N = map(int, input().split())
A = [0] * (loop_cnt + 1)

A_lis = list(map(int, input().split()))
for a in A_lis:
    A[a] += 1

Q = int(input())

ans = 0

for i in range(loop_cnt):
    ans += i * A[i]

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

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


def main():
    n = ni()
    a = na()
    nums = [0 for i in range(100001)]
    suma = 0
    for i in a:
        suma += i
        nums[i] += 1
    q = ni()
    for i in range(q):
        b,c = na()
        suma = suma + (c-b)*nums[b]
        nums[c] += nums[b]
        nums[b] = 0
        print(suma)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
Bs = []
for i in range(Q):
    Bs.append(list(map(int, input().split(' '))))
    
    
A_list = [0]*(10**5+1)
for i in A:
    A_list[i] += 1
    
sum_value = sum(A)
for B in Bs:
    b, c = B
    sum_value += A_list[b]*c
    sum_value -= A_list[b]*b
    
    A_list[c] += A_list[b]
    A_list[b] = 0
    print(sum_value)

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
s = sum(A)
from collections import defaultdict
d = defaultdict(int)
for a in A:
    d[a] += 1
for _ in range(Q):
    b, c = [int(x) for x in input().split()]
    delta = c * (d[b]) - b * d[b]
    s += delta
    print(s)
    d[c] += d[b]    
    d[b] = 0

Submission status: Accepted

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

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


from collections import defaultdict

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

s = sum(A)

for i in range(Q):
    num = dic[B[i]]
    diff = num * (C[i] - B[i])
    # print("diff: ", diff)
    s += diff

    dic[C[i]] += dic[B[i]]
    dic[B[i]] = 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 _ in range(Q)]

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

for b, c in BC:
    n = cnt[b]
    s -= b * n
    s += c * n
    cnt[c] += n
    cnt[b] = 0
    print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [0]*Q, [0]*Q
    for i in range(Q):
        B[i], C[i] = map(int, input().split())
    # 個数を持つ
    # Biの個数 O(1),C[i]の個数 O(1) 更新 O(1) 総和O(1)

    count = Counter(A)
    tot = sum(A)
    for i in range(Q):
        b = count[B[i]]
        c = count[C[i]]
        count[C[i]] += b
        count[B[i]] = 0
        tot = tot - B[i]*b + C[i]*b
        print(tot)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
bc=[list(map(int,input().split())) for i in range(q)]
memo = [0]*(100001)
for i in a:
    memo[i]+=1
ans=sum(a)
for i in range(q):
    b,c=bc[i][0],bc[i][1]
    heru=b*memo[b]
    hueru=c*memo[b]
    memo[c]+=memo[b]
    memo[b]=0
    ans = ans-heru+hueru
    print(ans)

Submission status: Accepted

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

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

ans = sum(a)    

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

Submission status: Accepted

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

count_list = [0 for i in range(10 ** 5 + 1)]
for i in range(len(A_list)):
    count_list[A_list[i]] += 1

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

Submission status: Accepted

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

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

S = sum(A)
C = Counter(A)
for _ in range(int(input())):
	b, c = map(int, input().split())

	S -= C[b] * b
	S += C[b] * c
	C[c] += C[b]
	C[b] = 0

	print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from sys import stdin,setrecursionlimit
import heapq,bisect,math,itertools,string,queue,datetime,copy
setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, stdin.readline().split()))

def main():
    N = int(input())
    Als = inpl()
    sm = sum(Als)
    dd = [0 for _ in range(10**5+1)]
    for a in Als:
        dd[a] +=1
    Q = int(input())
    order = []
    for _ in range(Q):
        b,c = inpl()
        order.append((b,c))

    for item in order:
        o1 = item[0]
        o2 = item[1]
        count = dd[o1]
        dif = count*(o2 - o1)
        sm += dif
        print(sm)
        dd[o1] = 0
        dd[o2] += count

main()

Submission status: Accepted

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


d = [0]*(10**5+1)
ans = 0
for i in range(N):
  d[A[i]] += 1
  ans += A[i]

for j in range(Q):
  ans = ans - d[B[j][0]]*B[j][0] + d[B[j][0]]*B[j][1]
  d[B[j][1]] += d[B[j][0]]
  d[B[j][0]] = 0
  print(ans)

Submission status: Accepted

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

ls = sorted(ls)
ans = sum(ls)
newls = [0]*(100000+1+1)
for p in ls:
  newls[p] += 1
ls = newls

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def input():
    return sys.stdin.readline().strip()


N = int(input())
A = list(map(int, input().split()))
cntr = Counter(A)
Q = int(input())
curr_sum = sum(A)
for _ in range(Q):
    B, C = map(int, input().split())
    if B in cntr:
        curr_sum += (C - B) * cntr[B]
        cntr[C] += cntr[B]
        del cntr[B]
    print(curr_sum)

Submission status: Accepted

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

m = {}
sum = 0

for a in A:
  m[a] = m.get(a, 0) + 1
  sum += a

L = []
for _ in range(Q):
  B, C = list(map(int, input().split()))
  if m.get(B, 0) != 0:
    m[C] = m.get(C, 0) + m[B]
    sum += (C - B) * m[B]
    m[B] = 0
  L.append(sum)

for l in L:  
  print(l)

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
# region fastio

BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def RL(): return map(int, sys.stdin.readline().rstrip().split())
def RLL(): return list(map(int, sys.stdin.readline().rstrip().split()))
def N(): return int(input())
def comb(n, m): return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0
def perm(n, m): return factorial(n) // (factorial(n - m)) if n >= m else 0
def mdis(x1, y1, x2, y2): return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')

# ------------------------------
# f = open('../input.txt')
# sys.stdin = f

def main():
    n = N()
    arr = RLL()
    dic = defaultdict(int)
    for i in arr: dic[i]+=1
    sm = sum(arr)
    q = N()
    for _ in range(q):
        b, c = RL()
        num = dic[b]
        dic[c]+=dic[b]
        dic[b] = 0
        sm = sm-b*num+c*num
        print(sm)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

e_dict = {}
for a in A:
    if a in e_dict.keys():
        e_dict[a] += 1
    else:
        e_dict[a] = 1

ans = sum(A)

for b, c in zip(B, C):
    keys = e_dict.keys()
    if b in keys:
        poped = e_dict.pop(b)
        gap = c - b
        ans += (gap * poped)

        if c in keys:
            e_dict[c] += poped
        else:
            e_dict[c] = poped

    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
arr=list(map(int,input().split()))
d=defaultdict(int)
for i in arr:
	d[i]+=1
total=sum(arr)
ans=""
for i in range(int(input())):
	b,c=map(int,input().split())
	total=total-d[b]*b
	total=total+d[b]*c
	d[c]+=d[b]
	d[b]=0
	ans+=str(total)+"\n"

print(ans)

Submission status: Accepted

Solution code:
S=lambda:input()
I=lambda:int(input())
L=lambda:list(map(int,input().split()))
LS=lambda:list(map(str,input().split()))

import sys
input=sys.stdin.readline
n=I()
a=L()
suma=sum(a)
dic={}
for i in a:
    if i in dic:
        dic[i]+=1
    else:
        dic[i]=1
q=I()
for i in range(q):
    b,c=L()
    if b not in dic:
        print(suma)
        continue
    if c not in dic:
        suma-=b*dic[b]
        dic[c]=dic[b]
        suma+=c*dic[c]
        del dic[b]
    else:
        suma-=b*dic[b]
        suma+=c*dic[b]
        dic[c]+=dic[b]
        del dic[b]
    print(suma)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os
import collections

# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    # 数値取得サンプル
    #   1行1項目 n = int(input())
    #   1行2項目 x, y = map(int, input().split())
    #   1行N項目 x = [list(map(int, input().split()))]
    #   N行1項目 x = [int(input()) for i in range(n)]
    #   N行N項目 x = [list(map(int, input().split())) for i in range(n)]

    # 文字取得サンプル
    #   1行1項目 x = input()
    #   1行1項目(1文字ずつリストに入れる場合) x = list(input())
    n = int(input())
    a_s = list(map(int, input().split()))

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

    # counter = list(collections.Counter(a_s))
    counter = [0 for i in range(100001)]

    for i in a_s:
        counter[i] += 1

    sum_val = sum(a_s)
    for query in query_s:
        sum_val += (query[1] * counter[query[0]]) - (query[0] * counter[query[0]])
        counter[query[1]] += counter[query[0]]
        counter[query[0]] = 0
        print(sum_val)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """4
1 2 3 4
3
1 2
3 4
2 4"""
        output = """11
12
16"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
1 1 1 1
3
1 2
2 1
3 5"""
        output = """8
4
4"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """2
1 2
3
1 100
2 100
100 1000"""
        output = """102
200
2000"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":
    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

A_dict = defaultdict(int)
for a in A_list:
    A_dict[a] += 1

total = sum(A_list)

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:


n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
bc = []
d = {}
suma = sum(a)
for nr in a:
    if nr not in d:
        d[nr] = 1
    else:
        d[nr] += 1

for i in range(q):
    bc = [int(i) for i in input().split()]
    b = bc[0]
    c = bc[1]
    if b not in d:
        print(suma)
        continue
    suma = suma + (c - b) * d[b]
    if c not in d:
        d[c] = d[b]
    else:
        d[c] += d[b]
    d[b] = 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 i in range(q)]

lis=[0 for i in range(10**5)]

for i in a:
    lis[i-1]+=1

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


for i in range(q):
    bi,ci=bc[i]
    s+=lis[bi-1]*(ci-bi)
    print(s)
    lis[ci-1]+=lis[bi-1]
    lis[bi-1]=0

Submission status: Accepted

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

ans = 0
for num, count in A.items():
    ans += (num * count)

for a, b in change:
    ans -= (a * A[a])
    temp = A[a]
    A[a] = 0
    A[b] += temp
    ans += (b * temp)
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
a = [0]*100000
for i in A:
    a[i-1] += 1
Q = int(input())

ans = sum(A)

q = []

for i in range(Q):
    B, C = list(map(int, input().split()))
    if a[B-1] >= 1:
        ans = ans - B*a[B-1] + C*a[B-1]
        a[C-1] += a[B-1]
        a[B-1] = 0
    q.append(ans)

for i in q:
    print(i)

Submission status: Accepted

Solution code:
N = int(input())

CNT = {}
S = 0

for a in map(int, input().split()):
    if not(a in CNT):
        CNT[a] = 0

    CNT[a] += 1
    S += a

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

    if B in CNT:
        cnt = CNT[B]
        del CNT[B]

        S -= B*cnt
        S += C*cnt
        
        if not(C in CNT):
            CNT[C] = 0

        CNT[C] += cnt
        
    print(S)

Submission status: Accepted

Solution code:
from collections import Counter

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

A_counter = Counter(A)
A_sum = sum(A)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N = int(input())
    A =list(map(int, input().split()))
    s = sum(A)
    d = defaultdict(lambda: 0)

    for v in A:
        d[v] +=1

    Q = int(input())

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import time
#from collections import deque, Counter, defaultdict
#from fractions import gcd
#import bisect
#import heapq
import math
start=time.time()
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
inf = 10**18
MOD = 1000000007
ri = lambda : int(input())
rs = lambda : input().strip()
rl = lambda : list(map(int, input().split()))
n=ri()
a=rl()
q=ri()
dp=[0]*(10**5+1)
bc=[]
for i in range(n):
    dp[a[i]]+=1
bc=[tuple(rl()) for i in range(q)]
ans=0
for i,j in enumerate(dp):
    ans+=i*j
  
for b,c in bc:
    ans+=-dp[b]*b+dp[b]*c
    print(ans)
    dp[c]+=dp[b]
    dp[b]=0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
ans = sum(A)
l = [0] * 100000
for i in A:
    l[i-1] += 1
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    ans += l[B-1] * (C - B)
    l[C-1] += l[B-1]
    l[B-1] = 0
    print(ans)