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=list(map(int,input().split()))
q=int(input())
dic={i:0 for i in range(100002)}
ans=0
for i in range(n):
    dic[a[i]]+=1
    ans+=a[i]
for i in range(q):
    b,c=map(int,input().split())
    dic[c]+=dic[b]
    ans+=dic[b]*(c-b)
    dic[b]=0
    print(ans)

Submission status: Accepted

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

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

ANS=0
for i in C:
    ANS+=i*C[i]
    
for qq in range(Q):
    B,X=map(int,input().split())
    ANS+=X*C[B]
    C[X]+=C[B]

    ANS-=B*C[B]
    del(C[B])
    print(ANS)

Submission status: Accepted

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

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

ANS=0
for i in C:
    ANS+=i*C[i]
    
for qq in range(Q):
    B,X=map(int,input().split())
    ANS+=X*C[B]
    C[X]+=C[B]

    ANS-=B*C[B]

    del(C[B])

    print(ANS)

Submission status: Accepted

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

import sys
# import time
# import math
# import numpy as np
# import scipy.sparse.csgraph as cs            # csgraph_from_dense(ndarray, null_value=inf), bellman_ford(G, return_predecessors=True), dijkstra, floyd_warshall
# import random                                # random, uniform, randint, randrange, shuffle, sample
# import string                                # ascii_lowercase, ascii_uppercase, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from datetime import date, datetime          # date.today(), date(year,month,day) => date obj; datetime.now(), datetime(year,month,day,hour,second,microsecond) => datetime obj; subtraction => timedelta obj
# from datetime.datetime import strptime       # strptime('2019/01/01 10:05:20', '%Y/%m/%d/ %H:%M:%S') returns datetime obj
# from datetime import timedelta               # td.days, td.seconds, td.microseconds, td.total_seconds(). abs function is also available.
# from copy import copy, deepcopy              # use deepcopy to copy multi-dimentional matrix without reference
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from fractions import Fraction               # Fraction(a, b) => a / b ∈ Q. note: Fraction(0.1) do not returns Fraciton(1, 10). Fraction('0.1') returns Fraction(1, 10)
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)



def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79e+308
    # inf = 2 ** 63 - 1             # (for fast JIT compile in PyPy) 9.22e+18
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def isp():   return input().split()
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n = ii()
    L = lmi()
    q = ii()
    command = [lmi() for _ in range(q)]

    d = defaultdict(int)
    for num in L:
        d[num] += 1
    S = sum(L)

    for b, c in command:
        b_num = d[b]
        S += (c - b) * b_num
        d[b] = 0
        d[c] += b_num
        print(S)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
rrmm = lambda n: [rrm() for _ in xrange(n)]

####

from collections import defaultdict as ddic

def solve(N, A, Q, queries):
    count = ddic(int)
    for x in A:
        count[x] += 1
    S = sum(A)
    for b, c in queries:
        ct = count[b]
        count[b] = 0
        count[c] += ct
        S += (c-b) * ct
        print S
        

N = rri()
A=rrm()
Q= rri()
queries = [rrm() for _ in xrange(Q)]
solve(N, A, Q, queries)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n = int(input())
al = list(map(int, input().split()))
al_sum = sum(al)
q = int(input())

num = [0]*10001
for a in al:
    num[a] += 1


for _ in range(q):
    bi, ci = map(int, input().split())

    al_sum += num[bi]*(ci - bi)
    num[ci] += num[bi]
    num[bi] = 0

    print(al_sum)

Submission status: Runtime Error

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

count_array = [0]*(10**5)
for i in range(N):
    count_array[As[i]] += 1

sum = 0
for i in range(len(As)):
    sum += As[i]

for i in range(Q):
    x,y = map(int,input().split())
    sum += count_array[x]*(y-x)
    print(sum)
    count_array[y] += count_array[x]
    count_array[x] = 0

Submission status: Runtime Error

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
su = sum(A)
print(counter)
lis = {}
for i in range(Q):
  B, C = map(int, input().split())
  su -= B * counter[B]
  su += C * counter[B]
  counter[C] += counter[B]
  counter[B] = 0
  print(su)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))
lis = [0] * (10**5)
Q = int(input())
for x in A:
  lis[x] += 1 * x
for i in range(Q):
  B, C = map(int, input().split())
  try:
    temp = lis[B] // B
    lis[B] = 0
    lis[C] += temp * C
  except:
    pass
  print(sum(lis))

Submission status: Runtime Error

Solution code:
N=int(input())
List = list(map(int, input().split()))
Row = int(input())
QList = []
for i in range (Row):
  QList.append(list(map(int, input().split())))
dictA ={}
res = 0
for i in range (N):
  dictA.setdefault(List[i],0) 
  dictA[List[i]] += 1
  res += List[i]
for i in range(Row):
  num = dictA[QList[i][0]] 
  res = res - dictA[QList[i][0]] * QList[i][0]
  dictA[QList[i][0]] = 0
  dictA[QList[i][1]] += num
  res += QList[i][1] * num
  print(res)

Submission status: Runtime Error

Solution code:
import collections
n = int(input())
arr = list(map(int,input().split()))
cnt = collections.defaultdict(int)
for val in arr:
    cnt[val] += 1
sums = sum(arr)
q = int(input())
for _ in range(q):
    b, c = map(int,input().split())
    diff = (c-b)*(cnt[b])
    sums += diff
    print(sums)
    cnt[c] += nt[b]
    cnt[b] = 0

Submission status: Runtime Error

Solution code:
N = int(input())
As = list(map(int, input().split()))
Q = int(input())
 
sumAs = 0
dictAs = [0] * 1E5
for i in range(len(As)):
  sumAs += As[i]
  dictAs[As[i] - 1] = 1


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

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
for _ in range([0]*Q):
    b, c = map(int, input().split())
    A[A==b] = c
    print(np.sum(A))

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    d = dict()
    for a in list(map(int, input().split())):
        d[a] = d.get(a, 0) + 1

    for _ in range(int(input())):
        b, c = map(int, input().split())
        temp = d.get(b, 0)
        d[b] -= temp
        d[c] = d.get(c, 0) + temp

        print(sum(k*v for k, v in d.items()))

main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

l = [0] * 10**5
tot = 0
for i in range(N) :
    l[A[i]]+=1
    tot += A[i]
for i in range(Q):
    s0 = S[i][0]
    s1 = S[i][1]
    tot += s1 * (l[s0] + l[s1]) - (s0 * l[s0] + s1*l[s1])
    l[s1] += l[s0]
    l[s0] = 0
    print(tot)

Submission status: Runtime Error

Solution code:
l = [0] * 10**5
tot = 0
for i in range(N) :
    l[A[i]]+=1
    tot += A[i]
for i in range(Q):
    s0 = S[i][0]
    s1 = S[i][1]
    tot += s1 * (l[s0] + l[s1]) - (s0 * l[s0] + s1*l[s1])
    l[s1] += l[s0]
    l[s0] = 0
    print(tot)

Submission status: Runtime Error

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

l = [0] * 10**5
s = set()
for i in range(N) :
    l[A[i]]+=1
    s.add(A[i])
for i in range(Q):
    s0 = S[i][0]
    s1 = S[i][1]
    l[s1] += l[s0]
    try:
        s.remove(s0)
        s.add(s1)
    except :
        pass
    l[s0] = 0
    tot = 0
    for j in s:
        tot += j * l[j]
    print(tot)

Submission status: Runtime Error

Solution code:
import array

N = int(input())
A = array.array('L', list(map(int, input().split())))
MAX = 10**5
X = array.array('L', [0]) * MAX
Y = array.array('L', range(MAX))

for i in range(len(A)): X[A[i]] += 1
    
Q = int(input())
cur = sum(array.array('L', (X[i]*Y[i] for i in range(len(X)))))

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

Submission status: Runtime Error

Solution code:

N = int(input())
A = array.array('L', list(map(int, input().split())))
MAX = 10**5
X = array.array('L', [0]) * MAX
Y = array.array('L', range(MAX))

for i in range(len(A)): X[A[i]] += 1
    
Q = int(input())
cur = sum(array.array('L', (X[i]*Y[i] for i in range(len(X)))))

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

Submission status: Runtime Error

Solution code:
import numpy as np
#import random
from numba import jit

@jit
def main():
    #N = 100000
    #A = random.choices(range(1, N), k=N)
    N = int(input())
    A = np.array(list(map(int, input().split())), dtype=np.uintc)
    MAX = 10**5
    X = np.zeros(MAX, dtype=np.uintc)
    Y = np.array(range(MAX), dtype=np.uintc)
    
    for i in range(len(A)): X[A[i]] += 1
    
    Q = int(input())
    #Q = MAX
    OUT = np.zeros(Q, dtype=np.uintc)
    for i in range(Q):
        [b, c] = list(map(int, input().split()))
        #b, c = random.choice(range(1, N)), random.choice(range(1, N))
        X[c] += X[b]
        X[b] = 0
        OUT[i] = int(np.sum(X*Y))
    return OUT

OUT = main()
print("\n".join(map(str, list(OUT))))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())))
MAX = 10**5
X = np.zeros(MAX)
Y = np.array(range(MAX))

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

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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline()
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
num = [0]*100000
s = sum(A)
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(100000):
    num[i] = A.count(i+1)
for i in range(Q):
    s += (C[i]-B[i])*num[B[i]-1]
    print(s)
    num[C[i]-1] += num[B[i]-1]
    num[B[i]-1] = 0

Submission status: Runtime Error

Solution code:
N = int(input())
A = input().split()
Q = int(input())
for q in range(Q):
  b, c = input().split()
  A = A.replace(b,c)
  An = list(map(int,A)
  print(sum(An))

Submission status: Runtime Error

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

asum = sum(a)
adic = {}

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


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

Submission status: Runtime Error

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

adic = {}

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


for i in range(q):
  b, c = input().split()
  if b in adic:
    adic[c] += adic.pop(b)
  print( sum(int(j)*int(adic[j]) for j in adic)  )

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
sums = sum(a)
d = {}

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

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

Submission status: Runtime Error

Solution code:
d = {}

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

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

Submission status: Runtime Error

Solution code:
n=int(input())
clist=list(map(int,input().split()))
q=int(input())
for i in range(q):
  b,c=input().split()
  b=int(b)
  c=int(c)
  clist[b-1]=c
  print(sum(clist))

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[int(i) for i in input().strip().split(" ")]
t=int(input())
dic={}
sum_array=0
for i in arr:
    dic[i]=dic.get(i,0)+1
    sum_array+=i
    

for _ in range(t):
    a,b=[int(i) for i in input().split(" ")]
    if b in dic:
        dic[b]+=dic[a]
    else:
        dic[b]=dic[a]
    
    sum_array+=dic[a]*(b-a)
    print(sum_array)
    dic[a]=0

Submission status: Runtime Error

Solution code:
n=int(input())
arr=[int(i) for i in input().strip().split(" ")]
t=int(input())
dic={}
sum_array=0
for i in arr:
    dic[i]=dic.get(i,0)+1
    sum_array+=i
    

for _ in range(t):
    a,b=[int(i) for i in input().split(" ")]
    if b in dic:
        dic[b]+=dic[a]
    else:
        dic[b]=dic[a]
    
    sum_array+=dic[a]*(b-a)
    print(dic,sum_array)
    dic[a]=0

Submission status: Runtime Error

Solution code:
def sum_dic(dic):
    ans=0
    for i in dic:
        ans+=dic[i]*i
    return ans

n=int(input())
arr=[int(i) for i in input().strip().split(" ")]
t=int(input())
dic={}
for i in arr:
    dic[i]=dic.get(i,0)+1
    

for _ in range(t):
    a,b=[int(i) for i in input().split(" ")]
    if b in dic:
        dic[b]+=dic[a]
    else:
        dic[b]=dic[a]
    dic[a]=0
    print(sum_dic(dic))

Submission status: Runtime Error

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

for i in range(Q):
  A.replace(X[i, 0], X[i, 1])
  print(sum(A))

Submission status: Runtime Error

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

for i in range(Q):
  A.replace(X[i, 0], X[i, 1])
  print(sum(A))

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int,input().split()))
q = int(input())
dic = {}
s = sum(a)
for i in range(1,10**5+1):
    if i in a:
        dic[i] = a.count(i)
    else:
        dic[i] = 0
lis=[]
for j in range(q):
    b,c = map(int,input().split())
    lis.append([b,c])

for p in lis
    s += (p[1]-p[0])*dic[p[0]]
    dic[p[1]] += dic[p[0]]
    dic[p[0]] = 0
    print(s)

Submission status: Runtime Error

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

summ=sum(a)
num=[a.count(i) for i in range(1,100000)]
for i in range(q):
    b,c=map(int,input().split())
    b_num=num[b]
    num[c] += num[b]
    num[b]=0
    summ +=(c-b)*b_num
    print(summ)

Submission status: Runtime Error

Solution code:
n=int(input())
r=list(map(int,input().split()))
m={}
for u in r:
  if u not in m:m[u]=0
  m[u] += 1
s=0
for k in m:s+=k*m[k]
for _ in range(int(input())):
  a,b=map(int,input().split())
  if a in m:
    s += (b - a) * m[a]
    m[b] += m[a]
    del m[a]
  print (s)

Submission status: Runtime Error

Solution code:
n=int(input())
r=list(map(int,input().split()))
m={}
for u in r:
  if u not in m:m[u]=0
  m[u] += 1
s=0
for k in m:s+=k*m[k]
for _ in range(int(input())):
  a,b=map(int,input().split())
  if a not in m:
  else:
    s += (b - a) * m[a]
    m[b] += m[a]
    del m[a]
  print (s)

Submission status: Runtime Error

Solution code:
import numpy as np
n = input()
a = input()

q = int(input())
while q>0:
    b,c = input().split()
    a=a.replace(b,c)
    d = a.split()
    d = np.array(d)
    d = d.astype(int)
    print(d.sum())
    q-=1

Submission status: Runtime Error

Solution code:
from collections import Counter
 
N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
S = sum(A)
 
for _ in range(int(input())):
    p, q = map(int, input().split())
    k = count[p]
    count[p] = 0
    count[q] += k
    S += (q - p) * k
    print(S)

Submission status: Runtime Error

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

s=sum(a)

#このコードはO(10**10)になる可能性があり、重すぎる
"""
for i in range(q):
  while b[i] in a:
    s+=c[i]-b[i]
    a.remove(b[i])
    a.append(c[i])
  print(s)
"""

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
a = [int(x) for x in input().split()]
q = int(input())
b = [0]*q
c = [0]*q
for i in range(q):
    bc = input().split()
    b[i] = int(bc[0])
    c[i] = int(bc[1])
a_max = max(a)
cnt = [0]*a_max
sum = 0
for i in range(a_max):
    m = i + 1
    cnt[i] = a.count(m)
    sum += m*a.count(m)
for i in range(q):
    sum += (c[i]-b[i])*cnt[b[i]-1] 
    cnt[c[i]-1] += cnt[b[i]-1]
    cnt[b[i]-1] = 0

    print(sum)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
N = int(input())
A=list(map(int,input().split()))
A.sort()
Q = int(input())
BC = [map(int, input().split()) for _ in range(Q)]
B, C = [list(i) for i in zip(*BC)]
sum=0
D=[0]*(10**5)
for i in range(N):
    sum+=A[i]
    D[A[i]]+=1
for i in range(Q):
    D[C[i]]+=D[B[i]]
    sum+=D[B[i]]*(C[i]-B[i])
    D[B[i]]=0
    print(sum)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

q = int(input())

m = {}

for i in range(100000):
  m[i] = 0

for e in a:
  m[e] += 1
  
ans = sum(a)

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

Submission status: Runtime Error

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())
N=[0]*(10**3+10)
s=0
for i in range(n):
    N[a[i]-1]+=1
    s+=a[i]
for i in range(q):
    s+=(c[i]-b[i])*N[b[i]-1]
    N[c[i]-1]+=N[b[i]-1]
    N[b[i]-1]=0
    print(s)

Submission status: Runtime Error

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

sm = sum(A)

for q in range(Q):
	ctb = A.count(B[q])
	sm += (C[q]-B[q])*ctb
	print(sm)

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
cnt=[0 for _ in range(100000)]
for aa in a:
  cnt[aa]+=1
total=0
for i in range(len(cnt)):
  total+= i* cnt[i]
for i in range(q):
  b,c=map(int,input().split())

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

Submission status: Runtime Error

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
cnt=[0 for _ in range(100000)]
for aa in a:
  cnt[aa]+=1
total=0
for i in range(len(cnt)):
  total+= i* cnt[i]
for i in range(q):
  b,c=map(int,input().split())
  cnt[c] += cnt[b]
  total-= cnt[b] * b
  total+= cnt[b] * c
  cnt[b]=0
  print(total)

Submission status: Runtime Error

Solution code:
import math
n,k=map(int,input().split())
a=[list(map(int,input().split())) for _ in range(n)]
l,r=-1,10**19
while r-l>1:
    m=(l+r)//2
    b=0
    for w,d in a:
        b+=(m-w+d)//d
    if b<k:
        l=m
    else:
        r=m
print(r+1)

Submission status: Runtime Error

Solution code:
A=[0]*(10**5+1)
for i in a:
	A[i]+=1

for bc in BC:
	diff= bc[1]-bc[0]
	SUM+=diff*A[bc[0]]
	A[bc[1]]+=A[bc[0]]
	A[bc[0]]-=A[bc[0]]
	print(SUM)

Submission status: Runtime Error

Solution code:
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
a=input_array()
q=int(input())
BC=[input_array() for _ in range(q)]
SUM=sum(a)

A=[0]*10**5
for i in a:
	A[i]+=1

for bc in BC:
	diff= bc[1]-bc[0]
	SUM+=diff*A[bc[0]]
	A[bc[1]]+=A[bc[0]]
	A[bc[0]]-=A[bc[0]]
	print(SUM)

Submission status: Runtime Error

Solution code:
import numpy as np
N=int(input())
A=np.array(list(map(int,input().split())))
Q=int(input())
somme=sum(A)
L=np.zeros(10**5+1)
for i in range(1,N+1):
    L[i]=sum(A==i)

for step in range(Q):
    b,c=map(int,input().split())
    somme=somme+(c-b)*L[b]
    L[c]=L[c]+L[b]
    print(int(somme))

Submission status: Runtime Error

Solution code:
import sys
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))

n = Ii()
a = Li()
sa = sum(a)
af = [0]*(10**5)
for i in a: 
  af[i]+=1
q = Ii()
for i in range(q):
  b,c = Mi()
  sa = sa + (c-b)*af[b]
  af[c] += af[b]
  af[b] = 0;
  print(sa)

Submission status: Runtime Error

Solution code:
import sys
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))

n = Ii()
a = Li()
sa = sum(a)
af = [0]*(10**5)
for i in a: 
  af[i]+=1
q = Ii()
for i in range(q):
  b,c = Mi()
  sa = sa + (c-b)*af[b]
  af[c] += af[b]
  af[b] = 0;
  print(sa)

Submission status: Runtime Error

Solution code:
'''
参考
https://drken1215.hatenablog.com/entry/2020/06/21/224900
'''
N = int(input())
A = list(map(int, input().split()))

INF = 10 ** 5
cnt = [0] * INF
total = 0

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

Q = int(input())
BC = []

for _ in range(Q):
    BC.append(list(map(int, input().split())))

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

Submission status: Runtime Error

Solution code:
'''
参考
https://drken1215.hatenablog.com/entry/2020/06/21/224900
'''
N = int(input())
A = list(map(int, input().split()))

INF = 10 ** 5
cnt = [0] * INF
total = 0

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

Q = int(input())

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

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
# A = np.array(_A,dtype='int')
Q = I()
BC = [LI() for _ in range(Q)]
# print(BC)

def convert(n):
    return d[n]

d = {1:1,2:2,3:3,4:4,5:5,6:6,7:7,8:8,9:9}
for i in range(Q):
    for key, value in d.items():
        if BC[i][0] == value:
            d[key]=BC[i][1]
    ans = np.array(list(map(convert,A)),dtype='int')
    print(ans.sum())


# ans = list(map(convert,A))
# for item in ans:
#     print(item)
# print('\n'.join(str(ans)))

#A,B = zip(*AB)
#Ap = np.array(A)
#C = np.zeros(N + 1)

# if ans:
#     print('Yes')
# else:
#     print('No')

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
 
alp = 'abcdefghijklmnopqrstuvwxyz'
def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(S())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])
 
_ = I()
xs = Is()
 
sss = 0
count = D(int)
for x in xs:
  sss += x
  count[x] += 1
  
q = I()
for _ in range(q):
  b, c = I()
  sss += (c - b) * count[b]
  print(sss)
  count[c] += count[b]
  count[b] = 0

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
 
alp = 'abcdefghijklmnopqrstuvwxyz'
def S(): return sys.stdin.readline().rstrip().split(' ')
def Ss(): return list(S())
def I(): return _I(S())
def Is(): return list(I())
def _I(ss): return map(int, ss) if len(ss) > 1 else int(ss[0])
 
_ = I()
xs = Is()

count = D(int)
for x in xs:
  count[x] += 1

q = I()
for _ in range(q):
  b, c = I()
  count[c] += count[b]
  count[b] = 0
  print(np.sum([k*v for k, v in count.items()]))

Submission status: Runtime Error

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=0
B=[0]*10**5
for i in A:
    S+=i
    B[i]+=1  #Bは要素数管理
Q=int(input())
C=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    S=S+(C[i][1]-C[i][0])*B[C[i][0]]
    B[C[i][1]]+=B[C[i][0]]
    B[C[i][0]]=0
    print(S)