Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

Solution code:
from collections import Counter
input = raw_input
n = int(input())
As = list(map(int, input().split(" ")))
nums = [0] * (10**5+1)

counter = Counter(As)
cur_sum = sum(As)

for key, val in counter.items():
    nums[key] = val

q = int(input())
for i in range(q):
    b, c = map(int, input().split(" "))

    num1 = counter[b]
    counter[b] = 0
    counter[c] += num1

    diff = (c - b) * num1

    cur_sum += diff
    print(cur_sum)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
B = Counter(A)
ans = sum(A)
Q = int(input())

#print(B)
for i in range(Q):
    b, c =map(int, input().split())
    x = B[b]
    if x == 0:
        print(ans)
        continue
    if c in B:
        B[c] += x 
    else:
        B[c] = x
    B.pop(b)
    ans = ans + (c - b) * x
    #print(B)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N =int(input())
A_n =list(map(int,input().split()))
Q =int(input())
B_n ,C_n=[],[]
for i in range(Q):
    B,C =map(int,input().split())
    B_n.append(B)
    C_n.append(C)

dic =Counter(A_n)

sum0 =sum(A_n)
for i in range(Q):
    count = dic[B_n[i]]
    sum0 += (C_n[i]-B_n[i])*count
    dic[B_n[i]] = 0
    dic[C_n[i]] += count
    print(sum0)

Submission status: Accepted

Solution code:
n = int(input())

a_list = [int(i) for i in input().split()]
q = int(input())

ary = [0 for _ in range((10**5) + 1)]

for i in a_list:
    ary[i] += 1

ans = []

f_ans = sum(a_list)
for _ in range(q):
    b, c = map(int, input().split())
    f_ans += (c-b)*ary[b]
    ary[c] += ary[b]
    ary[b] = 0

    ans.append(f_ans)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline = sys.stdin.buffer.readline
 
n = int(readline())
a = Counter(map(int, readline().split()))
q = int(readline())
L = []
for i in range(q):
  L.append(list(map(int, readline().split())))
 
s = sum(x * y for x, y in a.items())
for b, c in L:
  # print(a)
  if b in a:
    s += (c - b) * a[b]
    a[c] += a[b]
    del a[b]
  print(s)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
op = [0] * q
for i in range(q):
    op[i] = map(int, input().split())

from collections import Counter

counter = Counter(a)

_sum = [sum(k * counter[k] for k in counter)] + [0] * q
index = 1
for b, c in op:
    inc = 0
    if b in counter:
        inc = (c-b) * counter[b]
        if c in counter:
            counter[c] = counter[c] + counter[b]
        else:
            counter[c] = counter[b]
        del counter[b]
    _sum[index] = _sum[index-1] + inc
    print(_sum[index])
    index += 1

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
alist = set()
adic = {}
su = 0

for i in a:
    su += int(i)
    if int(i) in alist:
        adic[int(i)] = adic[int(i)] + 1
    else:
        alist.add(int(i))
        adic[int(i)] = 1

q = int(input())
ans = []

for i in range(q):
    s = input().split()
    b = int(s[0])
    c = int(s[1])
    if b in alist:
        if not(c in alist):
            adic[c] = 0
            alist.add(c)
        adic[c] = adic[c] + adic[b]
        su = su + (c * adic[b]) - (b * adic[b])
        adic[b] = 0

    ans.append(su)
for i in range(len(ans)):
    print(ans[i])

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
a = li()
q = ii()

s = sum(a)

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

for i in range(q):
    b,c = mi()

    if m[b] == 0:
        print(s)
    else:
        count = m[b]

        s = s + (c-b)*count
        print(s)

        m[c] += count
        m[b] = 0

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np
from collections import defaultdict

def main():
	n=II()
	A=LI()
	q=II()

	d=defaultdict(int)

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

	ans=sum(A)

	for _ in range(q):
		b,c=MI()
		ans+=(c-b)*d[b]
		d[c]+=d[b]
		d[b]=0
		#print(d)
		print(ans)



















if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n, r = open(0).read().split(maxsplit=1)
n = int(n)
*a, r = r.split(maxsplit=n)
a = list(map(int, a))
q, *bc = map(int, r.split())

d = {}
for x in a:
    if x in d:
        d[x] += 1
    else:
        d[x] = 1
ret = sum(a)
for i in range(0, min(q*2, len(bc)), 2):
    b = bc[i]
    c = bc[i+1]
    if b in d:
        v = d.pop(b)
        if c in d:
            d[c] += v
        else:
            d[c] = v
        ret += c * v - b * v
    #ret = sum([k * v for k, v in d.items()])
    print(ret)

Submission status: Accepted

Solution code:
import collections
N = int(input())

Line = [int(s) for s in input().split()]
c = collections.Counter(Line)

# print(c)
v = 0

for i in c:
    # print(i)
    v += i * c[i]
# print(v)    

Q = int(input())


for _ in range(Q):
    Line = [int(s) for s in input().split()]
    try:
        c[Line[1]] += c[Line[0]]
        
        # print(c[Line[1]],c[Line[0]])
        v += c[Line[0]] * (Line[1] - Line[0])
        c.pop(Line[0])
        # v += c[Line[0]] * (C[Line[1]-C[Line[0]]])
    except:
        pass
        
        # print('Error')
    # print(c)

    # s=0
    # for i in c:
    #     # print(i)
    #     s += i * c[i]
    print(v)

Submission status: Accepted

Solution code:
from collections import Counter

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

g = [0] * (10**5 + 3)
for i in a:
    g[i] += 1

ans = sum(a)
for i,j in bc:
    ans -= g[i]*i 
    ans += g[i]*j
    g[j] += g[i]
    g[i] = 0
    print(ans)

Submission status: Accepted

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    ans = 0
    for k, v in dic.items():
        ans += int(k)*v
    for i in BC:
        B, C = i[0], i[1]
        ans += - B*dic[B] + C*dic[B]
        dic[C] += dic[B]
        del dic[B]
        print(ans)

resolve()

Submission status: Accepted

Solution code:
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())

sum = 0
kazu = [0] * (10**5+1) 
for i in a:
    kazu[i] += 1
    sum += i
for i in range(q):
    cnt = kazu[b[i]]
    kazu[b[i]] = 0
    kazu[c[i]] += cnt
    sa = c[i] - b[i]
    sum += (sa * cnt)
    print(sum)

Submission status: Accepted

Solution code:
from collections import Counter

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

Acnt = Counter(A)

SUM = sum(A)

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

    cnt = Acnt[B]
    SUM -= B * cnt
    
    del Acnt[B]

    SUM += C * cnt
    Acnt[C] += cnt

    print(SUM)

Submission status: Accepted

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

import collections
cca = collections.Counter(a)

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

Submission status: Accepted

Solution code:
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint

#oo=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
# ko=list("abcdefghijklmnopqrstuvwxyz")

def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def main():
    n=int(input())
    a=list(map(int,input().split()))
    q=int(input())
    total=sum(a)
    memo = defaultdict(int)
    answer = 0
    ans=[]
    for i in range(n):
        memo[a[i]]+=1
    for i in range(q):
        b,c=map(int,input().split())
        temp1=memo[b]*b
        temp2=memo[b]*c
        ded=temp2-temp1
        ans.append(total+ded)
        total+=ded

        memo[c]+=memo[b]
        memo[b] = 0

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










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 _ in range(Q)] 
ans = [0]*(10**5+1)

for i in range (len(A)):
    ans[A[i]] += 1
maxlen = max(max(A),max(max(BC)))
S = 0
for i in range(maxlen+1):
        S += ans [i]*i
for i in range(Q):
    ans[BC[i][1]] += ans[BC[i][0]]
    S = S + ans[BC[i][0]] *BC[i][1] - ans[BC[i][0]]*BC[i][0]
    ans[BC[i][0]] = 0
    print(S)

Submission status: Accepted

Solution code:
n=int(input())
l=[int(k) for k in input().split()]
lnew={}
for i in l:
  if i in lnew:
    lnew[i]+=1
  else:lnew[i]=1
Sum=0
for num,val in lnew.items():
    Sum+=num*val
k=int(input())
for i in range(k):
  a,b=input().split()
  a=int(a)
  b=int(b)
  if a in lnew:
    Sum-=lnew[a]*a
    c=0
    if b in lnew:
      c=lnew[b]
      Sum-=lnew[b]*b
    lnew[b]=c+lnew[a]
    Sum+=lnew[b]*b
  lnew.pop(a,None)
  
  print(Sum)

Submission status: Accepted

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

table = [0] * 100010


for i in A:
    table[i] += 1

sum = 0

for i in A:
    sum += i

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split(" ")))
q = int(input())
b = []
c = []

for _ in range(q):
	bi, ci = list(map(int, input().split(" ")))
	b.append(bi)
	c.append(ci)

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

s = sum(a)
for i in range(q):
	if b[i] not in dic:
		print (str(s))
		continue
	s += (c[i]-b[i]) * dic[b[i]]
	dic[c[i]] = dic.get(c[i], 0) + dic[b[i]]
	del dic[b[i]]
	print (str(s))

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
ans = sum(a)
mylist = Counter(a)

q = int(input())
for _ in range(q):
    b, c = map(int,  input().split())
    try:
        b_cnt = mylist[b]
        try:
            c_cnt = mylist[c]
        except:
            c_cnt = 0
        ans += (int(c) - int(b)) * b_cnt
        del mylist[b]
        mylist[c] = b_cnt + c_cnt
    except:
        pass
    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    A = list(map(int, input().split()))
    q = int(input())
    import numpy as np
    A.sort()
    ans = sum(A)
    from bisect import bisect_left,bisect_right
    from collections import Counter
    count = Counter(A)
    for i in range(q):
        b,c = map(int, input().split())
        k = count[b]
        if k != 0:
            count[c] += count.pop(b)
        ans += (c-b)* k
        print(ans)


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 _ in range(q)]

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

sum = 0
for k in dic:
    v = dic[k]
    sum += k*v

for i in bc:
    if i[0] in dic:
        if i[1] in dic:
            dic[i[1]] += dic[i[0]]
        else:
            dic[i[1]] = dic[i[0]]
        o = (i[1]- i[0])*dic[i[0]]
        dic[i[0]] = 0
        sum += o
    print(sum)

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math  # gcdもあるよ
import collections
from collections import deque
from collections import defaultdict
from copy import deepcopy
from itertools import accumulate #リストを与えると累積和を返す
def input(): return sys.stdin.readline().rstrip()
from functools import lru_cache #メモ化

def main():
    n = int(sys.stdin.readline())
    a = list(map(int,sys.stdin.readline().split()))
    q = int(sys.stdin.readline())
    queue = [list(map(int,sys.stdin.readline().split())) for _ in range(q)]
    count = collections.Counter(a)
    #print(count)
    #print(list(count))
    ans = 0
    for k in count:
        ans += k * count[k]
    for b, c in queue:
        if  b in count:
            if c in count:
                count[c] += count[b]
                ans += (c - b) * count[b]
                del count[b]
            else:
                count[c] = count[b]
                ans += (c - b) * count[b]

                del count[b]
        print(ans)
    
    
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

ans = 0
for num in dic:
    ans += num * dic[num]

for i in range(Q):
    b, c = list(map(int, input().split()))
    x = 0
    if b in dic:
        x = dic.pop(b)
        if c in dic:    
            dic[c] += x
        else:
            dic[c] = x
    ans += x * (c-b)
    print(ans)

Submission status: Accepted

Solution code:
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())

    ans = sum(A)
    d = dict()
    for i, a in enumerate(A):
        d[a] = d.get(a, 0) + 1

    for b, c in zip(B, C):
        if b not in d:
            print(ans)
            continue
        ans += d[b] * (c-b)
        if c not in d:
            d[c] = 0
        d[c] = d[c] + d[b]
        d[b] = 0
        print(ans)

main()

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int,input().split()))
S = sum(A)
c = collections.Counter(A)

Q = int(input())

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

Submission status: Accepted

Solution code:
class Counter(dict):
    def __missing__(self, i):
        return 0

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

#print(n, a, q)
total = sum(a)
#print("total", total)

bucket = Counter()

for item in a:
    bucket[item] += 1

#print("bucket", bucket)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
for n in range(N):
    B[n+1] = B[n] + A[n]
C = B.pop()

Z = {}
for n in range(N):
    Z[A[n]] = 0
for n in range(N):
    Z[A[n]] += 1

D = []
Q = int(input())
for q in range(Q):
    x, y = map(int, input().split())
    if x in Z:
        C = C - x*Z[x]
        C = C + y*Z[x]
        D.append(C)
        if x == y:
            continue
        if y in Z:
            Z[y] += 1*Z[x]
        else:
            Z[y] = Z[x]
        Z.pop(x)
    else:
        D.append(C)
for d in D:
    print(d)

Submission status: Accepted

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

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

d = collections.Counter(A)
ans = 0
for k, v in d.items():
    ans += k * v

for i in range(Q):
    B,C = list(map(int, input().split()))
    if B in d:
        val = d[B]
        ans -= B * d[B]
        ans += C * d[B]
        if C in d:
            d[C] = d[C] + d[B]
        else:
            d[C] = d[B]
        d.pop(B)

    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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 = [0] * (10 ** 5 + 1)
s = sum(A)
for a in A:
    t[a] += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

_ = sys.stdin.readline()
A = list(map(int, sys.stdin.readline().split()))
Q = int(sys.stdin.readline())
replace_map = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

nums = {}
for a in A:
    nums[a] = nums[a] + 1 if a in nums else 1

previous_sum = 0
for search, replace in replace_map:
    replaced_count = 0
    if search in nums:
        replaced_count = nums[search]
        nums[replace] = nums[replace] + replaced_count if replace in nums else replaced_count
        del nums[search]
    if previous_sum == 0:
        previous_sum = np.dot(list(nums.keys()), list(nums.values()))
    else:
        previous_sum += replaced_count * (replace - search)
    print(previous_sum)

Submission status: Accepted

Solution code:
#d
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())
D = [0] * (10**5+1)
ans=sum(A)
for i in A:
    D[i]+=1
for x in range(Q):
    ans+=D[B[x]]*int(C[x]-B[x])
    print(ans)
    D[C[x]]+=D[B[x]]
    D[B[x]]=0

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
arr={}
P={}
for a in A:
	if a in arr:
		arr[a]+=1
	else:
		arr[a]=1
for k,v in arr.items():
	P[k]=k*v
S=sum([i for i in P.values()])
Q=int(input())
for q in range(Q):
	B,C=[int(i) for i in input().split()]
	if B in arr:
		if C in arr:
			arr[C]+=arr[B]
			P[C]+=arr[B]*C
		else:
			arr[C]=arr[B]
			P[C]=arr[B]*C
		S-=P[B]
		S+=arr[B]*C
		del arr[B]
		del P[B]
	print(S)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = list(map(int, input().split()))
q = int(input())
b = []
for x in range(q):
    b.append(list(map(int, input().split())))

hikaku = 0
a_wa = sum(a)
cou = collections.Counter(a)
for i in range(q):
    a_wa += cou[b[i][0]] * b[i][1] - cou[b[i][0]] * b[i][0]
    cou[b[i][1]] += cou[b[i][0]]
    cou[b[i][0]] = 0

    print(a_wa)

Submission status: Accepted

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

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

#print(bc)

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

def s_sum(dd):
    res = 0
    for k,v in dd.items():
        res += k * v
    return res

wk = s_sum(d)

for ss in bc:
    b = ss[0]
    c = ss[1]

    b_cnt = d[b]
    c_cnt = d[c]
    d[b] = 0
    d[c] += b_cnt
    wk = wk + b_cnt*c - b_cnt*b
    print(wk)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections
N = int(input())
A = list(map(int, input().split()))
A_amount = dict(collections.Counter(A))

result = sum(A)

Q = int(input())
for q in range(Q):
    B, C = map(int, input().split())
    B_elem = A_amount.get(B, None)
    if B_elem is not None:
        C_elem = A_amount.get(C, None)
        if C_elem is not None:
            A_amount.pop(B)
            A_amount[C] = B_elem+C_elem
        else:
            A_amount.pop(B)
            A_amount[C] = B_elem

        result += (C-B)*B_elem

    print(result)

Submission status: Accepted

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



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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [0 for _ in range(100001)]
for x in a:
  b[x] += 1
ans = sum(a)
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  ans += (y-x) * b[x]
  b[x],b[y] = 0,b[x]+b[y]
  print(ans)

Submission status: Accepted

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

B = []
C = []

l = {}

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

    B.append(b)
    C.append(c)

res = 0
for i in A:
    if i in l:
        l[i] += 1
    else:
        l[i] = 1

    res += i

t = 0
for i in range(Q):
    if B[i] in l:
        t = l[B[i]]


        res += (C[i] - B[i]) * t

        l[B[i]] = 0
        if C[i] in l:
            l[C[i]] += t
        else:
            l[C[i]] = t

    print(res)

Submission status: Accepted

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

num_count = [0]*(10**5+1)
num_count = np.array(num_count)
tmp = np.arange(10**5+1)
tmp_sum = sum(A)
for i in A:
    num_count[i] += 1

for q in range(Q):
    B,C = map(int,input().split())
    tmp_C = C*(num_count[B])
    tmp_B = B*(num_count[B])
    num_count[C] += num_count[B]
    num_count[B] = 0
    tmp_sum = tmp_sum + tmp_C - tmp_B
    print(tmp_sum)

Submission status: Accepted

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

Bl = [0] * Q
Cl = [0] * Q

for _ in range(Q):
    B, C = map(int, input().split())
    CONV[B] = C
    Bl[_] = B
    Cl[_] = C

# print("conv", CONV)
from collections import defaultdict
VAL = defaultdict(int)

for a in A:
    VAL[a] += 1
# print("DEF:", VAL)
DEF = 0
for i, j in VAL.items():
    DEF += i * j
# DEF = sum(VAL.keys())
# print("DEFAULT:", DEF)
for qi in range(Q):
    k = Bl[qi]
    v = Cl[qi]
    if k in VAL.keys():
        DEF += -k*VAL[k] + v*VAL[k]
        VAL[v] += int(VAL[k])
        # print("VAL[{}]={}".format(v, VAL[k]))
        del VAL[k]
    print(DEF)
    # print(VAL)

# ans = 0
# for val, cnt in VAL.items():
#     ans += val * cnt

# print(ans)

Submission status: Accepted

Solution code:
import io,sys
sys.setrecursionlimit(10**6)

def main():
    from collections import Counter
    n = input()
    A = list(map(int,sys.stdin.readline().rstrip().split()))

    C = Counter(A)
    s = 0
    for k,v in C.items():
        s += k*v

    q = int(input())
    for _ in range(q):
        b,c = map(int,sys.stdin.readline().rstrip().split())
        s = s - C[b]*(b-c) 
        C[c]+=C[b]
        C[b]=0

        print(s)
main()

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = [int(each) for each in input().split()]
q = int(input())
rep = [tuple(int(each) for each in input().split()) for i in range(q)]

s = [sum(a)]

c = collections.Counter(a)
for i in range(q):
    diff = (rep[i][1]-rep[i][0])
    num = c.get(rep[i][0])
    if not num:
        num = 0
    # print('i:', i)
    # print(c)
    # print('差分:', diff, '個数:', num)
    s.append(s[-1]+num*diff)

    # 存在しないときにエラーになる
    if c.get(rep[i][0]):
        c[rep[i][1]] += c.pop(rep[i][0])

print('\n'.join([str(each) for each in s[1:]]))

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]
from collections import Counter
cntr = Counter(A)
ans = sum(A)
for b, c in Query:
    if cntr.get(b) == None:
        print(ans)
        continue
    diff = (c - b) * cntr[b]
    ans += diff
    print(ans)
    cntr[c] += cntr[b]
    cntr[b] = 0

Submission status: Accepted

Solution code:
def sumdic(dic):
  s=0
  for k, v in dic.items():
    s+=int(k)*v
  return s

a=int(input())
dic={}
for x in input().split():
  if x in dic:
    dic[x]+=1
  else:
    dic[x]=1
s=sumdic(dic)
d=int(input())
for i in range(d):
  (b,c)=[x for x in input().split()]
  if c in dic and b in dic:
    dic[c]+=dic[b]
    s+=(int(c)-int(b))*dic[b]
    dic.pop(b)
  elif b in dic:
    dic[c]=dic[b]
    s+=(int(c)-int(b))*dic[b]
    dic.pop(b)
  print(s)

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''
    N = int(input())
    A_list = [int(item) for item in input().split()]
    Q = int(input())
    queries = [[int(item) for item in input().split()] for _ in range(Q)]

    memo = [0 for _ in range(10**5+1)]

    for item in A_list:
        memo[item] += 1
        

    base = sum(A_list)

    for b, c in queries:
        memo[c] += memo[b]
        base = base + memo[b]*c - memo[b]*b
        memo[b] = 0
        print(base)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

dicts = {}
for tmp in a:
  if tmp in dicts.keys():
    dicts[tmp] += 1
  else:
    dicts[tmp] = 1
    
m = int(input())
result = 0
for key, value in dicts.items():
  result += key*value

for _ in range(m):
  b,c = list(map(int, input().split()))
  if b in dicts.keys():
    tmp = dicts[b]
    diff = dicts[b]*b
    add = tmp*c
    
    del dicts[b]
    if c in dicts.keys():
      dicts[c] += tmp
      
    else:
      dicts[c] = tmp
      
    result -= diff
    result += add
    print(result)
  else:
    print(result)

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
info = []
for i in range(q):
    info.append(list(map(int, input().split())))

a_dict = dict()
for num in a:
    if num in a_dict.keys():
        a_dict[num] += 1
    else:
        a_dict[num] = 1

a_key = list(a_dict.keys())
a_value = list(a_dict.values())
ans = 0
for k in range(len(a_dict)):
    ans += a_key[k] * a_value[k]

for j in range(q):
    if info[j][0] in a_dict.keys():
        if info[j][1] in a_dict.keys():
            ans -= info[j][0] * a_dict[info[j][0]]
            ans += info[j][1] * a_dict[info[j][0]]
            a_dict[info[j][1]] += a_dict[info[j][0]]
            del a_dict[info[j][0]]
        else:
            ans -= info[j][0] * a_dict[info[j][0]]
            a_dict[info[j][1]] = a_dict[info[j][0]]
            ans += info[j][1] * a_dict[info[j][1]]
            del a_dict[info[j][0]]


    print(ans)