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
n=int(input())
a=list(map(int,input().split()))
q=int(input())
s=sum(a)
d=Counter(a)
for i in range(q):
    b,c=map(int,input().split())
    if b in d:
        l=d[b]
        d[b]=0
        d[c]+=l
        s+=(c-b)*l
        print(s)
    else:print(s)

Submission status: Accepted

Solution code:
n = int(input())

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

ans = sum(ans_lst)

val_dic = {}
for i in ans_lst:
  if i in val_dic:
    val_dic[i] += 1
  else:
    val_dic[i] = 1


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

  if b in val_dic:
    z = val_dic[b]
  
  ans = ans + (c - b) * z
  print(ans)

  if b in val_dic:
    num = val_dic[b]
    val_dic[b] = 0
    if c in val_dic:
      val_dic[c] += num
    else:
      val_dic[c] = num

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n = i_input()
    num_list = i_list()
    q = i_input()
    current_sum = sum(num_list)
    cnt_list = Counter(num_list)
    # print(cnt_list)
    # print(current_sum)

    # print('----')

    for _ in range(q):
        b, c = i_map()
        b_cnt = cnt_list[b]
        cnt_list[b] = 0
        cnt_list[c] += b_cnt
        current_sum += (c-b) * b_cnt
        print(current_sum)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

ctr = Counter(A)
sum_ini = sum(A)

for b, c in query:
    x = ctr[b]
    ctr[c] += x
    ctr[b] -= x
    sum_ini += (c - b) * x
    print(sum_ini)

Submission status: Accepted

Solution code:
n=int(input())
l=[0]*10**5
A=list(map(int,input().split()))

for a in A:
    l[a-1]+=1

ans=sum(A)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
N = int(input())
A = list(map(int, input().split()))
count = Counter(A)
count = dict(count)
Q = int(input())
# Q回の処理を行う, i回目の操作では, 値がBiであるものを全てCiに置き換える
now = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    if b not in count:
        print(now)
    else:
        if c not in count:
            count[c] = 0
        now += (c-b) * count[b]
        print(now)
        count[c] += count[b]
        count[b] = 0

Submission status: Accepted

Solution code:
import collections

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

c = collections.Counter(a)

s = sum(a)
for bi, ci in bc:
    if bi not in c:
        print(s)
    else:
        s = s - c[bi] * bi + c[bi] * ci
        print(s)
        if ci in c:
            c[ci] = c[ci] + c[bi]
            c[bi] = 0
        else:
            c[ci] = c[bi]
            c[bi] = 0

Submission status: Accepted

Solution code:
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
from collections import deque
import collections
import heapq
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
q=[list(map(int,input().split())) for _ in range(Q)]
nums={}
su=sum(A)
#print(q)
for i in range(N):
    if nums.get(A[i])==None:
        nums[A[i]]=1
    else:
        nums[A[i]]=nums[A[i]]+1
#print(nums)
for i in range(Q):
    b,c=q[i]
    bnum=nums.pop(b,None)
    cnum=nums.pop(c,None)
    #print(anum,bnum)
    if bnum!=None:
        if cnum!=None:
            su=su+(c-b)*bnum
            nums[c]=cnum+bnum
            print(su)
        else:
            su = su + (c - b) * bnum
            nums[c]=bnum
            print(su)
    else:
        if cnum!=None:
            nums[c]=cnum
        print(su)
    #print(nums)

Submission status: Accepted

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

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

for i in BC:
    ans += (i[1] - i[0]) * dp[i[0]]
    dp[i[1]] += dp[i[0]]
    dp[i[0]] = 0
    print(ans)

Submission status: Accepted

Solution code:
R = lambda: map(int, input().split())
R()
a = [0] * 100001
s = 0
for x in R():
  s += x
  a[x] += 1
q, = R()
for _ in range(q):
  b, c = R()
  s += (c - b) * a[b]
  print(s)
  a[c]+=a[b]
  a[b] = 0

Submission status: Accepted

Solution code:
from sys import stdin, stdout
from collections import Counter
for _ in range(1):#int(stdin.readline())
    n=int(stdin.readline())
    a=list(map(int, stdin.readline().split()))
    d=Counter(a);s=sum(a)
    q=int(stdin.readline())
    for qq in range(q):
        old,new=map(int, stdin.readline().split())
        times=d[old]
        s+=times*(new-old)
        d[old]=0
        d[new]=d.get(new,0)+times
        print(s)

Submission status: Accepted

Solution code:
n = int(input())
m = {}
tot = 0
for a in map(int,input().split()):
  tot += a
  if a not in m:
    m[a]=0
  m[a] += 1
q = int(input())
for step in range(q):
  b,c = map(int,input().split())
  if c not in m:
    m[c] = 0
  if b in m:
    m[c] += m[b]
    tot += m[b]*(c-b)
    m[b] = 0
  print(tot)

Submission status: Accepted

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

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

ans = sum(a)
a = Counter(a)
for b, c in bc:
    ans += (c - b) * a[b]
    a[c] += a[b]
    a[b] = 0
    print(ans)

Submission status: Accepted

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


d = {a: 0 for a in set(A)}
for a in A:
    d[a] += 1

ans = sum(A)
for b, c in zip(B, C):
    if b not in d.keys():
        print(ans)
        continue

    ans += c * d[b] - b * d[b]

    if c not in d.keys():
        d[c] = 0
    d[c] += d[b]
    del d[b]

    print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    N = int(sys.stdin.readline())
    A = list(map(int, sys.stdin.readline().split()))
    Q = int(sys.stdin.readline())
    BC = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]
    C = Counter(A)
    '''
    L = [0 for _ in range(10**5+1)]
    for key, value in C.items():
        L[key] = value
    '''
        
    ans = 0
    for bc in BC:
        C[bc[1]] += C[bc[0]]
        tmp = C[bc[0]]
        C[bc[0]]= 0
        #print(C)
        if ans == 0:
            for key, value in C.items():
                ans += key*value
        else:
            ans +=(bc[1]-bc[0])*tmp
        print(ans)
        



if __name__=='__main__':
    main()

Submission status: Accepted

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

q = int(input())

memo = {}

for a in A:
    if a in memo:
        memo[a] += 1
    else:
        memo[a] = 1

total = sum(A)

for i in range(q):
    b, c = map(int, input().split())
    if b not in memo:
        memo[b] = 0
    if c not in memo:
        memo[c] = 0

    total += (c - b) * memo[b]

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

    print(total)

Submission status: Accepted

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

    # ls.append([int(j) for j in input().split()])

Submission status: Accepted

Solution code:
import numpy as np
N = int(input())
A = [int(x) for x in input().split(" ")]
Q = int(input())

S = 0

query = []
for _ in range(Q):
    query.append([int(x) for x in input().split(" ")])

array = np.zeros(10**5, dtype=int)
for a in A:
    S += a
    array[a-1] += 1

# print("Q: ", Q)
for B, C in query:
    # print(array)
    D = array[B-1]
    S += (C - B) * D
    print(S)
    array[C-1] += D
    array[B-1] = 0
# print(array)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
l=[]
for _ in range(Q):
    l.append(list(map(int,input().split())))
c = collections.Counter(A)
sum=sum(A)
for i in range(Q):
    if c[l[i][0]] == 0:
        print(sum)
        continue
    else:
        sum+=c[l[i][0]]*(l[i][1]-l[i][0])
        c[l[i][1]]+=c[l[i][0]]
        del c[l[i][0]]
        print(sum)

Submission status: Accepted

Solution code:
import bisect
from collections import defaultdict
d = defaultdict(int)
n=int(input())
a=list(map(int,input().split()))
q=int(input())
a.sort()
for key in a:
  d[key] += 1
#print(d)
wa=sum(a)
for i in range(q):
  b,c=map(int,input().split())
  if d[b]>0:
    d[c]+=d[b]
    wa+=d[b]*(c-b)
    d[b]=0
  print(wa)

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in input().split()]
Q=int(input())
X=[i+1 for i in range((10**5))]
dic={}
ans=sum(A)
for i in A:
	try:
		dic[i]+=1
	except:
		dic.setdefault(i,1)
for i in range(Q):
	[B,C]=[int(i) for i in input().split()]
	try:
		ans+=dic[B]*(C-B)
		try:
			dic[C]+=dic[B]
		except:
			dic.setdefault(C,dic[B])
		dic[B]=0
	except:
		ans+=0
	print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

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

import collections
c = collections.Counter(a)

m=sum(a)
for i in range(q):
    m+=c[l[i][0]]*(l[i][1]-l[i][0])
    print(m)

    b=c[l[i][0]]
    c[l[i][0]]=0
    c[l[i][1]]+=b

Submission status: Accepted

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

dictA = {}

for z in A:
    dictA.setdefault(z, 0)
    dictA[z] += 1

sumA = sum(A)

BC = [list(map(int, input().split())) for i in range(Q)]
for x in BC:
    if x[0] in dictA.keys():
        sumA += (x[1] - x[0]) * dictA[x[0]]
        dictA.setdefault(x[1], 0)
        dictA[x[1]] += dictA[x[0]]
        dictA.pop(x[0])
    print(sumA)

Submission status: Accepted

Solution code:

N = int(input())
*A, = map(int, input().split())
cnt = [0]*(10**5+1)
s = 0
for i in range(N):
    cnt[A[i]] += 1
    s += A[i]

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

Submission status: Accepted

Solution code:
#n,k=map(int,input().split())
from collections import defaultdict
n=int(input())
l=list(map(int,input().split()))
d=defaultdict(int)
s=0
for i in l:
  d[i]+=1
  s+=i

q=int(input())
for _ in range(q):
  a,b=map(int,input().split())
  temp=a*d[a]
  if temp==0:
    print(s)
  else:
    k=b*d[a]
    s+=k-temp
    print(s)
    d[b]+=d[a]
    del d[a]

Submission status: Accepted

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


cnt = defaultdict(int)
s = 0
for a in A:
  cnt[a] += 1
  s += a
 
for i in range(Q):
  b,c = map(int,input().split())
  s = s - b*cnt[b] + c*cnt[b]  
  cnt[c] += cnt[b]
  cnt[b] = 0
  #print(cnt)
  print(s)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    nums = defaultdict(int)
    for i in range(N):
        nums[A[i]] +=1
    s = 0
    for key in nums.keys():
        s += nums[key] * key
    for i in range(Q):
        count = nums[B[i]]
        nums[C[i]]+=nums[B[i]]
        nums[B[i]] = 0
        s = s - count*B[i] + count*C[i]
        print(s)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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 Counter
N = int(input())
a = list(map(int, input().split()))
Q = int(input())
bc = [list(map(int, input().split())) for _ in range(Q)]
tmp_counter = Counter(a)
tmp_sum = sum(a)
for b, c in bc:
    if b in tmp_counter.keys():
        tmp_sum += (c - b) * tmp_counter[b]
        tmp_counter[c] += tmp_counter[b]
        tmp_counter[b] = 0
    print(tmp_sum)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
#print()
#print(N)
#print(A)
#print(Q)
#print()
counterA = dict(Counter(A))
counterAkeys=set(counterA.keys())
#print(counterAkeys)

sumA = sum(A)

#print(sumA,counterA)
for _ in range(Q):
  b,c=map(int,input().split())
  #print(b,c)
  if b not in counterAkeys:
    print(sumA)
    continue
  b_cnt = counterA[b]
  counterA[b]=0
  if c in counterAkeys:
    counterA[c] += b_cnt
  else:
    counterA[c] = b_cnt
    counterAkeys.add(c)

  sumA+=(c-b)*b_cnt
  print(sumA)

Submission status: Accepted

Solution code:

import sys 
input=sys.stdin.readline 
def getsum(BITTree,i): 
	s = 0 
	i = i+1
	while i > 0: 
		s += BITTree[i] 
		i -= i & (-i) 
	return s 
def updatebit(BITTree , n , i ,v): 
	i += 1
	while i <= n: 
		BITTree[i] += v 
		i += i & (-i) 
def construct(arr, n): 
	BITTree = [0]*(n+1) 
	for i in range(n): 
		updatebit(BITTree, n, i, arr[i]) 
	return BITTree 
n=int(input())
arr=[int(i) for i in input().split()]
from collections import Counter 
c=Counter(arr)
m=int(input())
sm=sum(arr)
for i in range(m): 
    a,b=map(int,input().split())
    if c[a]:
        sm-=c[a]*a 
        sm+=c[a]*b 
        c[b]+=c[a]
        c[a]=0 
    print(sm)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Jun 21 21:34:50 2020

@author: NEC-PCuser
"""
import collections

N = int(input())

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

list_sum = sum(A)

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

for i in sum_list:
    print(i)

Submission status: Accepted

Solution code:
import sys
import numpy as np

if __name__ == '__main__':
    n = int(sys.stdin.readline().rstrip())
    A = list(map(lambda x: int(x), sys.stdin.readline().split()))
    q = int(sys.stdin.readline().rstrip())
    dic = {}
    for a in A:
        dic[a] = dic.get(a, 0) + 1

    # keys = list(dic.keys())
    # values = list(dic.values())
    # summ = np.array(keys).dot(np.array(values))
    summ = sum([k*v for k, v in dic.items()])
    for i in range(q):
        b, c = list(map(lambda x: int(x), sys.stdin.readline().split()))

        diff = c*dic.get(b,0) - b*dic.get(b,0)
        dic[c] = dic.get(c, 0) + dic.get(b, 0)
        dic[b] = 0
        summ += diff
        print(summ)

Submission status: Accepted

Solution code:


def main():
    N = int(input())
    a = list(map(int, input().split()))
    Q = int(input())
    maxa = max(a)
    x = [0] * ((10**5)+1)
    ans = 0
    for i in range(0, N):
        e = a[i]
        x[e] += 1
        ans += e
    for j in range(Q):
        b, c = list(map(int, input().split()))
        ans += (c - b) * x[b]
        x[c] += x[b]
        x[b] = 0
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
N = int(input())
A = list(map(int, input().split()))
s = sum(A)
d = {}
for i in range(N):
    if A[i] in d.keys():
        d[A[i]] += 1
    else:
        d[A[i]] = 1
Q = int(input())
for i in range(Q):
    b, c = map(int, input().split())
    if b not in d.keys() or d[b] == 0:
        pass
    else:
        tmp = d[b]
        s -= d[b] * b
        s += d[b] * c
        d[b] = 0
        if c in d.keys():
            d[c] += tmp
        else:
            d[c] = tmp
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
x = list(map(int,input().split()))
c = Counter(x)
y=[0]*(10**5+1)
for i in c.keys():
	y[i]=c[i]
ad=0
su=sum(x)
q=int(input())
for i in range(q):
	b , c = map(int, input().split())
	su=su-y[b]*b+y[b]*c
	y[c]+=y[b]
	y[b]=0
	print(su)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
change = []
for i in range(q):
  change.append(list(map(int, input().split())))
dict = Counter(a)
ans = sum(a)
ans_list = []
for b, c in change:
  if b in dict.keys():
    if c in dict.keys():
      dict[c] += dict[b]
      ans = ans + (c-b)*dict[b]
      dict[b] = 0
      ans_list.append(ans)
    else:
      dict[c] = dict[b]
      ans = ans + (c-b)*dict[b]
      dict[b] = 0
      ans_list.append(ans)
  else:
    ans_list.append(ans)
for i in ans_list:
  print(i)

Submission status: Accepted

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

import collections as cl

def main() :
    N = int(input())
    A_list = [int(i) for i in input().split()]
    current_sum = sum(A_list)

    # 数のバリエーションが多いと詰むなあ
    c = cl.Counter(A_list)
    # print(c)
    # print(c[1])
    # c[1] = 100
    # print(c[1])
    Q = int(input())
    for i in range(Q) :
        B,C = map(int,input().split())
        diff = C-B
        num = c[B]
        current_sum += diff * num
        c[B] = 0
        c[C] += num
        print(current_sum)

main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def read():
    return sys.stdin.readline().rstrip()


def main():
    n = int(read())
    a = Counter(map(int, read().split()))
    s = sum(k * v for k, v in a.items())
    q = int(read())
    for _ in range(q):
        b, c = map(int, read().split())
        k = a[b]
        a[b] = 0
        a[c] += k
        s += (c - b) * k
        print(s)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import Counter
    n = int(readline())
    a = list(map(int, readline().split()))
    q = int(readline())
    counter = Counter(a)
    res = sum(a)

    for i in range(q):
        b, c = map(int, readline().split())
        res -= counter[b] * b
        res += counter[b] * c
        counter[c] += counter[b]
        counter[b] = 0
        print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
d = {}
for i in l:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1
sumz = sum(l)
for _ in range(int(input())):
    b,c = map(int, input().split())
    if b in d:
        sumz = sumz +( ((d[b]*c) - (d[b]*b)) )
        if c not in d:
            d[c] = d[b]
        else:
            d[c] += d[b]
        del d[b]
    print(sumz)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = [int(x) for x in input().split()]
BC = [(int(x) for x in input().split()) for _ in range(int(input()))]
ans = sum(A)
cnts = Counter(A)
for b, c in BC:
    b_num = cnts[b]
    c_num = cnts[c]
    ans += (c - b) * cnts[b]
    print(ans)
    cnts[c] = cnts[c] + cnts[b]
    cnts[b] = 0

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = list(map(int, input().split()))
    C = Counter(A)
    Q = int(input())
    ans = sum(A)
    for _ in range(Q):
        b,c = map(int, input().split())
        x = C[b]
        ans += (c-b) * x
        C[b] = 0
        C[c] += x
        print(ans)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = [int(i) for i in input().split()]
A = [0]*(1+(10**5))
num = 0
for l in L:
    A[l] += 1
    num += l
Q = int(input())
for _ in range(Q):
    B,C =[int(i) for i in input().split()]
    num += (C-B)*A[B]
    A[C] += A[B]
    A[B] = 0
    print(num)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

sum_a = sum(A)
c = Counter(A)
for i in range(q):
    b_num = c[B[i]]
    diff = (C[i] - B[i]) * b_num
    c[C[i]] = c[C[i]] + c[B[i]]
    c[B[i]] = 0
    sum_a = sum_a + diff
    print(sum_a)

Submission status: Accepted

Solution code:
from collections import Counter


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
n_data = Counter(A)
ans = sum(A)
for _ in range(Q):
  b, c = map(int, input().split())
  ans += (c - b) * n_data[b]
  n_data[c] += n_data[b]
  n_data[b] = 0
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
List = list(map(str, input().split()))
Q = int(input())
x = [0] * Q
y = [0] * Q
for i in range(Q):
    x[i], y[i] = map(str, input().split())
    y[i]=int(y[i])

wa=0
for i in List:
    wa+=int(i)
c =Counter(List)
for i in range(Q):
    num=c['{}'.format(x[i])]
    wa+=num*(y[i]-int(x[i]))
    c['{}'.format(x[i])]=0
    c['{}'.format(str(y[i]))]+=num
    print(wa)

Submission status: Accepted

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

Submission status: Accepted

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

main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
query = [list(map(int, input().split())) for i in range(Q)]

Asum = sum(A)
Adict = Counter(A)

for q in query:
  before = q[0]
  after = q[1]
  if before in Adict:
    Asum += (after-before) * Adict[before]
    if after in Adict:
      Adict[after] += Adict.pop(before)
    else:
      Adict[after] = Adict.pop(before)
  print(Asum)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
s=sum(a)
q=int(input())
b=[]
c=[]
for i in range(q):
    xb,xc=map(int,input().split())
    b.append(xb)
    c.append(xc)
r=[0]*1000001
for i in a:
    r[i]+=1
for i in range(q):
    y=r[b[i]]
    r[b[i]]=0
    r[c[i]]+=y
    s+=y*(c[i]-b[i])
    print(s)

Submission status: Accepted

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

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

from collections import Counter
cnt = Counter(a)

ans = [sum(a)]

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = dict()
total = sum(A)
for a in A:
    d[a] = d.get(a, 0) + 1
Q = int(input())
res = [-1] * Q
for i in range(Q):
    b, c = map(int, input().split())
    cnt = d.get(b, 0)
    total -= (b - c) * cnt
    d[c] = d.get(c, 0) + cnt
    d[b] = 0
    res[i] = total
print(*res, sep='\n')

Submission status: Accepted

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

Submission status: Accepted

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

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

for i in range(N):
  a = List[i]
  arr[a] += 1
  S += int(a)
  
for i in range(Q):
  a,b = map(int,input().split())
  aa = arr[a]
  arr[b] += aa
  arr[a] = 0
  S += int ( (b-a) * aa )
  print(int(S))

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    A = list(map(int, input().split()))
    cA = defaultdict(int)
    sv = sum(A)
    for a in A:
        cA[a] += 1
    Q = int(input())
    for _ in range(Q):
        bi, ci = map(int, input().split())
        sv -= cA[bi] * bi
        sv += cA[bi] * ci
        cA[ci] += cA[bi]
        del cA[bi]
        # print(sv, cA)
        print(sv)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
s = 0
A2 = {}
for i in range(N):
  s += A[i]
  k = str(A[i])
  if k not in A2:
    A2[k] = 1
  else:
    A2[k] += 1

for i in range(Q):
  b,c = map(str,input().split())
  if b in A2:
    l = A2[b]
    s += l*(int(c)-int(b))
    print(s)
    A2.pop(b)
    if c in A2:
      A2[c] += l
    else:
      A2[c] = l
  else:
    print(s)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
def input():
    return sys.stdin.readline()[:-1]
def main():
    N = int(input())
    A = list(map(int,input().split()))
    D = [0]*100001
    for e in A:
        D[e] += 1
    Q = int(input())
    ans = sum(A)
    for _ in range(Q):
        B, C = map(int,input().split())
        if D[B] > 0:
            t = D[B]
            D[B] = 0
            D[C] += t
            ans += (C-B)*t
        print(ans)
if __name__ == '__main__':
    main()