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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

dic = Counter(A)
su = sum(A)
ans = []
for _ in range(Q):
    B, C = MAP()
    su -= dic[B]*B
    su += dic[B]*C
    dic[C] += dic[B]
    dic[B] = 0
    ans.append(su)
print(*ans, sep="\n")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve():
    ret = sum(A)
    dict_A = {}
    for a in A:
        dict_A[a] = dict_A.get(a, 0) + 1
    for i in range(Q):
        tmp = dict_A.get(B[i], 0)
        ret -= tmp * B[i]
        dict_A[B[i]] = 0
        dict_A[C[i]] = dict_A.get(C[i], 0) + tmp
        ret += C[i] * tmp
        print(ret)

if __name__ == "__main__":
    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)
    solve()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    a = nl()
    m = 10**5 + 5
    l = [0]*m
    s = 0
    for x in a:
        l[x] += 1
        s += x
    q = ni()
    for _ in range(q):
        b, c = nm()
        v = l[b]
        s += (c - b)*v
        l[b] = 0
        l[c] += v
        print(s)
    return

solve()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
ns = list(map(int, input().split()))
C = Counter(ns)
s = sum(key * value for key, value in C.items())
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
import math

# import copy
# from bisect import bisect_left, bisect_right
# import heapq

# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 998244353

def solve():
    n = getN()
    nums = getList()
    d = defaultdict(int)
    for num in nums:
        d[num] += 1
    ans = sum(nums)
    # print(d)
    Q = getN()
    for i in range(Q):
        b, c = getList()
        if b in d and d[b] > 0:
            ans -= b * d[b]
            ans += c * d[b]
            d[c] += d[b]
            d[b] = 0

        print(ans)



def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

d = collections.defaultdict(int)

S = sum(A)

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

for B, C in BC:
    diff = C - B
    S += d[B]*diff
    d[C] += d[B]
    d[B] = 0
    print(S)

Submission status: Accepted

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

N_list=[0]*(100001)
sumn=0

for a in a_list:
    N_list[a]+=1
    sumn+=a


for i in range(Q):
    b,c=map(int,input().split())
    henka=(c-b)*N_list[b]

    sumn+=henka

    N_list[c]+=N_list[b]
    N_list[b]=0

    print(sumn)

Submission status: Accepted

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

N = int(input())
dict_number = {}
S = 0

for a in map(int, input().split()):
  S += a
  if a in dict_number.keys():
    dict_number[a] += 1
  else:
    dict_number[a] = 1

Q = int(input())
for _ in range(Q):
  B,C = map(int, input().split())
  if B in dict_number.keys():
    b = dict_number.pop(B)
    S += b*(C-B)
    if C in dict_number.keys():
      dict_number[C] += b
    else:
      dict_number[C] = b
  print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
import collections
import copy
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
MOD = 10**9+7

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

S = sum(A)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
ans = sum(A)
d = defaultdict(lambda:0)
for i in range(N):
    d[A[i]] += 1

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

for i in range(Q):
    b,c = BC[i]
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
ACMOD = 1000000007
INF = 1 << 62


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    _sum = sum(A)
    ac = collections.Counter(A)
    for i in range(Q):
        b, c = B[i], C[i]

        diff = ac[b] * (c - b)
        _sum += diff
        ac[c] += ac[b]
        ac[b] = 0
        print(_sum)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)


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


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

SUM = sum(A)


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

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())
    
cnt = [0]*(10**5+3)
for i in A:
    cnt[i]+=1
ans = sum(A)
for i in range(Q):
    ans += (C[i]-B[i])*cnt[B[i]]
    print(ans)
    cnt[C[i]] += cnt[B[i]]
    cnt[B[i]] = 0

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
# import numpy as np
sys.setrecursionlimit(int(pow(10,6)))
# sys.stdin = open("input.txt", "r")
# sys.stdout = open("output.txt", "w")
mod = int(pow(10, 9) + 7)
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(*var, end="\n"): sys.stdout.write(' '.join(map(str, var))+end)
def l(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# @lru_cache(None)
n=l()[0]
A=l()
d=[0 for i in range(10**5+1)]
s=0
for i in range(n):
    d[A[i]]+=1
    s+=A[i]
q=l()[0]
for i in range(q):
    b,c=l()
    s+=(c-b)*d[b]
    print(s)
    d[c]+=d[b]
    d[b]=0

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from collections import defaultdict, Counter

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""
dicで各要素の数を保持
"""
N = ir()
A = lr()
Q = ir()
counter = Counter(A)
dic = defaultdict(int)
for k, v in counter.items():
    dic[k] = v

total = sum(A)
answer = []
for _ in range(Q):
    b, c = lr()
    num = dic[b]
    total -= num * b
    total += c * num
    dic[b] = 0
    dic[c] += num
    answer.append(total)

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

Submission status: Accepted

Solution code:

from collections import defaultdict
from typing import DefaultDict

from collections import defaultdict

N = int(input())
A = [int(i) for i in input().split()]
di_A = defaultdict(int)

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

Q = int(input())
now_sum = sum(A)
ans = []
for _ in range(Q):
    b, c = [int(i) for i in input().split()]
    cnt = di_A[b]
    now_sum += cnt * (c-b) 
    di_A[b] = 0
    di_A[c] += cnt
    ans.append(now_sum)

for a in ans:
    print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    n = int(input())
    a = tuple([int(t)for t in input().split()])
    s = sum(a)

    c = Counter(a)

    ans = []
    q = int(input())
    for _ in range(q):
        x,y = tuple([int(t)for t in input().split()])
        s += (y-x)*c[x]
        ans.append(s)
        c[y] += c[x]
        c[x] = 0

    for a_i in ans:
        print(a_i)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(1000000)

import bisect
import math
import collections
import heapq


def solve(N, As, Q, BCs):
    # print(N, ",", As, ",", Q, ",", BCs)
    counter = collections.Counter(As)
    current_sum = sum(As)
    ans = []
    for b, c in BCs:
        if b in counter:
            original = counter[b] * b
            to = counter[b] * c
            diff = to - original
            current_sum += diff
            if c not in counter:
                counter[c] = 0
            counter[c] += counter[b]
            del counter[b]
        ans.append(str(current_sum))
    return "\n".join(ans)


# print(solve(4, [1, 2, 3, 4], 3, [(1, 2), (3, 4), (2, 4)]))

if __name__ == "__main__":
    N = int(input())
    As = list(map(int, input().split(" ")))

    Q = int(input())
    BCs = [tuple(map(int, input().split(" "))) for _ in range(Q)]

    print(solve(N, As, Q, BCs))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from collections import Counter
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input())
    a = [int(ai) for ai in input().split()]
    ca = Counter(a)

    s = sum(a)

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


# 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")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

ans = sum(t)

memo = [0]*100001

for i in t:
    memo[i] += 1

s=int(input())
for _ in range(s):
    b, c = (int(x) for x in input().split())
    ans += (c-b)*memo[b]
    print(ans)
    memo[c] += memo[b]
    memo[b] = 0

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)]
a.sort
count=[0 for _ in range(1000000)]
sum=0
for i in range(n):
  count[a[i]]=count[a[i]]+1
  sum=sum+a[i]
for i in range(q):
  sum=sum+(c[i]-b[i])*count[b[i]]
  print(sum)
  count[c[i]]=count[c[i]]+count[b[i]]
  count[b[i]]=0

Submission status: Accepted

Solution code:
import sys 
from collections import defaultdict
input = lambda:sys.stdin.readline().strip()
n = int(input())
a = list(map(int,input().split()))
a_s = sum(a)
freq = defaultdict(int)
for i in a:
    freq[i]+=1
q = int(input())
while q:
    q-=1
    bi,ci = map(int,input().split())
    new_a_s = a_s+freq[bi]*(ci-bi)
    print(new_a_s)
    freq[ci]+=freq[bi]
    freq[bi]=0
    a_s = new_a_s

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    C = Counter(map(int, input().split()))
    total = 0
    for key, val in C.items():
        total += key * val

    for _ in range(int(input())):
        b, c = map(int, input().split())
        k = C[b]
        total += k * (c - b)
        C[b] = 0
        C[c] += k
        print(total)
resolve()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = [[int(i) for i in input().split()] for j in range(Q)]

    cA = [0]*(10**5+1)
    for a in A:
        cA[a] += 1
    sumA = sum(A)
    for b, c in BC:
        miA = cA[b]*b
        plA = cA[b]*c
        cA[c] += cA[b]
        cA[b] = 0
        sumA -= miA
        sumA += plA
        print(sumA)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Contest No.: ABC171
# Problem No.: D
# Solver:      JEMINI
# Date:        20200621

import sys
import heapq

def main():
    n = int(input())
    nums = list(map(int, sys.stdin.readline().split()))
    cntList = [0] * (10 ** 5 + 1)
    for i in range(n):
        cntList[nums[i]] += 1
    sumVal = sum(nums)
    q = int(input())
    for _ in range(q):
        b, c = map(int, sys.stdin.readline().split())
        sumVal -= cntList[b] * b
        sumVal += cntList[b] * c
        cntList[c] += cntList[b]
        cntList[b] = 0
        print(sumVal)

    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

d = {}
for a in A:
    if a not in d.keys():d[a] = 0
    d[a] += 1
s = sum(A)
q = int(input())
for i in range(q):
    b,c = map(int,input().split())
    if b in d.keys():
        s += d[b]*(c-b)
        if c not in d.keys():d[c] = 0
        d[c] += d[b]
        d[b] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    Q=int(input())
    S = tuple(tuple(map(int, input().split())) for i in range(Q)) #改行行列
    ca=Counter(A)
    tot=sum(A)
    for B,C in S:
        red=ca[B]
        ca[B]=0
        ca[C]+=red
        tot+=red*(C-B)
        print(tot)





if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from math import log
def main():
    n = int(input())
    a = [int(j) for j in input().split()]
    d = [0]*100001
    for i in range(n):
        d[a[i]]+=1
    q = int(input())
    s = sum(a)
    for i in range(q):
        b,c =[int(j) for j in input().split()]
        tmp = d[b]
        d[b] = 0
        d[c] += tmp
        s += tmp*(c-b)
        print(s)

    # for t in range(int(input())):
        # n = int(input())
        

# "Ashishgup" if he wins, and "FastestFinger"

# for #!/usr/bin/env python
# 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")

# # endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter as ct

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
a = list(map(int, input().split()))
q = int(input())
s = sum(a)
from collections import Counter, defaultdict
tmp = Counter(a)
c = defaultdict(int)
c.update(tmp)
ans = [None]*q
for i in range(q):
    bb,cc = map(int, input().split())
    if bb in c:
        s = s + (cc-bb) * c[bb]
        v = c.pop(bb)
        c[cc] += v
    ans[i] = s
write("\n".join(map(str, ans)))

Submission status: Accepted

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

all_sum = sum(A)
cnt = {}
for a in A:
    if a not in cnt:
        cnt[a] = 0
    cnt[a] += 1
    


for (b,c) in queries:
    if b in cnt:
        all_sum -= b * cnt[b]
        all_sum += c * cnt[b]
        if c not in cnt:
            cnt[c] = 0
        cnt[c] += cnt[b]
        cnt[b] = 0
    print(all_sum)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
has = defaultdict(int)
arr = list(map(int, input().split(" "))) 
ans = 0
for a in arr :
    has[a] += 1
    ans += a

Q = int(input())
for i in range(Q) :
    b, c = map(int ,input().split(" "))
    ans -= has[b]*b
    ans += has[b]*c

    has[c] += has[b]
    has[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = [None for _ in range(q)]
    for i in range(q):
        bc[i] = list(map(int, input().split()))

    count = [0 for i in range(100001)]
    for i in range(n):
        count[a[i]] += 1

    ans = [0 for _ in range(q+1)]
    for i in range(100001):
        ans[0] += i * count[i]
    for i in range(q):
        ans[i+1] = ans[i] - count[bc[i][0]] * bc[i][0] + count[bc[i][0]] * bc[i][1]
        count[bc[i][1]] += count[bc[i][0]]
        count[bc[i][0]] = 0

    for i in range(1, q+1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

for _ in range(Q):
    B, C = map(int, readline().split())
    d.setdefault(B, 0)
    d.setdefault(C, 0)
    t -= B * d[B]
    t += C * d[B]
    d[C] += d[B]
    d[B] = 0
    print(t)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ikutu = [0]*10**5
for i in range(N):
    ikutu[A[i]-1] += 1
Q = int(input())
total = sum(A)
ans = [0]*Q
for i in range(Q):
    B, C = map(int, input().split())
    if ikutu[B-1] == 0:
        ans[i] = total
    else:
        total += (C-B)*ikutu[B-1]
        ikutu[C-1]+= ikutu[B-1]
        ikutu[B-1] = 0
        ans[i] = total
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))
d = {}
ans = sum(A)
for a in A:
    if a in d:
        d[a]+=1
    else:
        d[a]=1




Q = int(input())

BC = []

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

for b, c in BC:
    if b in d:
        ans += (c-b)*d[b]
        tmp = d[b]
        d[b] = 0
        if c in d:
            d[c] += tmp
        else:
            d[c] = tmp
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

def main():
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    S = sum(A)
    Q = int(input())
    for _ in range(Q):
        b, c = map(int, input().split())
        nb = C.get(b, 0)
        S += nb * (c - b)
        if b in C:
            del C[b]
        C[c] = C.get(c, 0) + nb
        print(S)
main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
pairs = list(tuple(map(int, input().split())) for _ in range(Q))

init_sum = sum(A)
counter = Counter(A)
total = init_sum

for b, c in pairs:
    total -= counter[b] * b
    total += counter[b] * c
    counter[c] += counter[b]
    del counter[b]
    print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    s = sum(A)
    d = Counter(A)
    Q = int(input())
    for i in range(Q):
        b, c = map(int, input().split())
        if b in d:
            s += (c - b) * d[b]
            d[c] = d.get(c, 0) + d[b]
            d[b] = 0
        print(s)
main()

Submission status: Accepted

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

from collections import Counter

su=sum(a)
cnt=Counter(a)

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

Submission status: Accepted

Solution code:
from collections import Counter

from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))

n=int(input())
a=lnii()

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

q=int(input())
for i in range(q):
  b,c=nii()

  b_cnt=count[b]

  if b_cnt!=0:
    count[b]=0
    if c in count:
      count[c]+=b_cnt
    else:
        count[c]=b_cnt

  t_ans=ans-(b*b_cnt)+(c*b_cnt)
  ans=t_ans
  print(t_ans)