Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
 
def Main():
    n = I()
    a = list(IL())
    C = Counter(a)
    m = sum(a)
    q = I()
    s = []
    for rep in range(q):
        b,c = IL()
        if b in C:
            m += (c-b)*C[b]
            C[c] += C[b]
            C[b] = 0
        s.append(m)
    for rep in s:
        print(rep)
    return
 
if __name__=='__main__':
    Main()

Submission status: Accepted

Solution code:
import collections as C
n = int(input())
a = list(map(int, input().split()))
q = int(input())
d = C.Counter(a)
ans = sum(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    Q, *BC = map(int, read().split())

    total = sum(A)
    d = [0] * (10 ** 5 + 1)
    for a in A:
        d[a] += 1

    for b, c in zip(*[iter(BC)] * 2):
        total += (c - b) * d[b]
        d[c] += d[b]
        d[b] = 0
        print(total)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    Q, *BC = map(int, read().split())

    total = sum(A)
    d = [0] * (10 ** 5 + 1)
    for a in A:
        d[a] += 1

    for b, c in zip(BC[::2], BC[1::2]):
        total += (c - b) * d[b]
        d[c] += d[b]
        d[b] = 0
        print(total)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def main():
    n = int(input())

    aa = input_ints()
    m = defaultdict(lambda: 0)
    s = 0
    for a in aa:
        m[a] += 1
        s += a

    q = int(input())
    for _ in range(q):
        b, c = tuple(input_ints())
        s += (c - b) * m[b]
        m[c] += m[b]
        del m[b]
        print(s)


main()

Submission status: Accepted

Solution code:
nb=int(input())
liste = [int(x) for x in input().split()]
liste2= [0]*((10**5)+1)
for loop in range(len(liste)):
  liste2[liste[loop]] +=1
nba = int(input())
somme = sum(liste)
for loop in range(nba):
  n,r = map(int,input().split())
  roger = liste2[n]
  diff = r-n
  somme += diff * roger
  liste2[r] += liste2[n]
  liste2[n] = 0
  print(somme)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
cnt = collections.Counter(a)
sm = sum(a)
res = []
for i in range(q):
    b, c = map(int, input().split())
    sm += cnt[b] * (c - b)
    res.append(sm)
    cnt[c] += cnt[b]
    cnt[b] = 0
for r in res:
    print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
C = [0] * 100001
s = 0
for i in A:
    C[i] += 1
    s += i

K = int(input())

for i in range(K):
    f, t = map(int, input().split())
    C[t] += C[f]
    s += t * C[f]
    s -= f * C[f]
    C[f] = 0
    print(s)

Submission status: Accepted

Solution code:
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()
Q = int(input())
BC = [LI() for _ in range(Q)]

MAX = 10 ** 5


def main():
    d = {i: 0 for i in range(MAX + 1)}
    s = 0
    for a in A:
        d[a] += 1
        s += a
    for b, c in BC:
        x = d[b]
        s += (c - b) * x
        print(s)
        d[c] += d[b]
        d[b] = 0


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, *i = map(int, open(0).read().split())
    a = i[:n]
    _ = i[n]
    s = sum(a)

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

    ans = []
    for b, c in zip(*[iter(i[n + 1:])] * 2):
        m[c] += m[b]
        s += (c - b) * m[b]
        m[b] = 0
        ans.append(s)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n, *i = map(int, open(0).read().split())
    a = i[:n]
    _ = i[n]
    s = sum(a)

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

    ans = []
    for b, c in zip(*[iter(i[n + 1:])] * 2):
        m[c] += m[b]
        s += (c - b) * m[b]
        m[b] = 0
        ans.append(s)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
sys.setrecursionlimit(10**2)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
# NUMBER = 10**9 + 7
NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k))))
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 


def solution(a,n,Q,q):
	d = defaultdict(int)
	for x in a:
		d[x]+=1
	s = sum(a)
	res = []
	for b,c in Q:
		s+=(c-b)*d[b]
		d[c]+=d[b]
		d[b] = 0
		res.append(str(s))
	return '\n'.join(res)
	
def main():
	T = 1
	# T = ri()
	for i in range(T):
		# s = rs()
		n = ri()
		a = ria()
		q = ri()
		Q = []
		for _ in range(q):
			Q.append(ria())
		# n,k = ria()
		# a=ria()

		x = solution(a,n,Q,q)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			print >>output,str(x)# "Case #"+str(i+1)+':',
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

#print(BC)
yoso_count=[]
for i in range(1,10**5+1):
    yoso_count.append([i,0])

sum = 0
for a in A:
    yoso_count[int(a)-1][1] += 1
    sum += a

#print(yoso_count,sum)

for bc in BC:
    sum += (bc[1] - bc[0])*yoso_count[bc[0]-1][1]
    yoso_count[bc[1]-1][1] += yoso_count[bc[0]-1][1]
    yoso_count[bc[0]-1][1] = 0
    print(sum)

Submission status: Accepted

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

numlist = [0] * int(1e5 + 5)
for t in a:
    numlist[t] += 1
ans = sum(a)

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

Submission status: Accepted

Solution code:
INT_MAX=10**11+7
MOD=10**9+7
def INPUT():return list(int(i) for i in input().split())
def LIST_1D_ARRAY(n):return [0 for _ in range(n)]
def LIST_2D_ARRAY(m,n):return [[0 for _ in range(n)]for _ in range(m)]
GETA=12
#import sys,os,multiprocessing
#print(3)
###############################################################################\
n=int(input())
A=INPUT()
D=[0]*(10**5+1)
for ele in A:
    D[ele]+=1
s=0
for i in range(10**5+1):
    s+=D[i]*i
for i in range(int(input())):
    b,c=INPUT()
    if D[b]!=0:
        if D[c]!=0:
            s+=(c-b)*(D[b])
            D[c]+=D[b]
            D[b]=0
        else:
            D[c]=D[b]
            s+=(c-b)*D[c]
            D[b]=0
    print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter(a)
sum_res = sum(a)  # 初期状態の合計、名前がsumだとsum関数とかぶってよくないので

# q回操作します。ループ変数は使わないので_にします（Pythonの慣習）
for _ in range(q):
    before, after = map(int, input().split())
    
    # 和を計算します
    sum_res -= before * counter[before]
    sum_res += after * counter[before]
    
    # 個数を変更します
    counter[after] += counter[before]
    counter[before] = 0
    
    print(sum_res)

Submission status: Accepted

Solution code:
n = int(input())
l=list(map(int,input().split()))
d={}
s=0
for i in range(n):
    s+=l[i]
    if (l[i] in d):
        d[l[i]]+=1
    
    else:
        d[l[i]]=1
    
k = int(input())
for j in range(k):
    a,b=(map(int,input().split()))
    if a in d:
        s=s-d[a]*a+d[a]*b
        if b in d:
            d[b]+=d[a]
        else:
            d[b]=d[a]
        d.pop(a)
        print(s)
    else:
        print(s)

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

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

tot = sum(a)

for i in range(q):
    if cnt[b[i]] > 0:
        tot += cnt[b[i]] * (c[i] - b[i])
        cnt[c[i]] += cnt[b[i]]
        cnt[b[i]] = 0
    print(tot)

Submission status: Accepted

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

ans = sum(A)
 
Q = int(input())

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

Submission status: Accepted

Solution code:
import collections

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

collect_dict = dict(collections.Counter(a))

now = sum(a)

ans = []
for i in range(q):
    b, c = map(int,input().split())
    if b not in collect_dict.keys():
        ans.append(now)
        continue
    now -= collect_dict[b] * b
    tmp = collect_dict[b]
    collect_dict.pop(b)
    if c not in collect_dict.keys():
        collect_dict[c] = 0
    collect_dict[c] += tmp
    now += c * tmp
    ans.append(now)

for i in ans:
    print(i)

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    sum_a = sum(a)
    kk = [0] * (10 ** 5 + 1)
    for i in a:
        kk[i] += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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)]
goukeiti=sum(A)
atai=[0]*(10**5+1)
for i in A:
    atai[i-1]+=1
for i in BC:
    kotae=atai[i[0]-1]*i[1]-atai[i[0]-1]*(i[0])
    atai[i[1]-1]+=atai[i[0]-1]
    atai[i[0]-1]=0
    goukeiti+=kotae
    print(goukeiti)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, = map(int, input().split())
from collections import defaultdict
A = list(map(int, input().split()))
d = defaultdict(int)
for a in A:
    d[a] += 1
R=0
for k in d:
    R += k*d[k]
Q, = map(int, input().split())
for _ in range(Q):
    a, b = map(int, input().split())
    d[b] += d[a]
    R = R + (b-a)*d[a]
    d[a] = 0
    print(R)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
dic = collections.Counter(a)
sum_list = [x * y for (x, y) in dic.items()]
sum = sum(sum_list)
for i in range(q):
    b, c = map(int, input().split())
    if b in dic and c not in dic:
        sum -= (b - c) * dic[b]
        print(sum)
        dic[c] = dic[b]
        del dic[b]
    elif b in dic and c in dic:
        sum -= (b - c) * dic[b]
        print(sum)
        dic[c] += dic[b]
        del dic[b]
    else:
        print(sum)

Submission status: Accepted

Solution code:
from collections import defaultdict

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)


counter = defaultdict(int)
now_sum = 0

for a in A:
    counter[a] += 1
    now_sum += a

for i in range(Q):
    b = B[i]
    c = C[i]

    changed_count = counter[b]
    changed_sum = changed_count * (c - b)
    now_sum += changed_sum
    
    counter[c] += counter[b]
    counter[b] = 0

    print(now_sum)

Submission status: Accepted

Solution code:
N = int(input())
ls = [0 for i in range(10**5)]
now = 0
A = list(map(int,input().split()))
for i in range(N):
    now += A[i]
    ls[A[i]-1] += 1
q = int(input())
for i in range(q):
    a,b = map(int,input().split())
    now += (b-a)*ls[a-1]
    print(now)
    ls[b-1] += ls[a-1]
    ls[a-1] = 0

Submission status: Accepted

Solution code:
from collections import *

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

A_dic = Counter(A)
A_sum = sum(A)

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

Submission status: Accepted

Solution code:
from collections import *
from operator import mul

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


A_dic = Counter(A)
A_sum = sum(A)

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

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = input()
    a = [int(v) for v in input().split()]
    count = dict(Counter(a))
    q = int(input())

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# D - Replacing
def main():
    N, *X = map(int, open(0).read().split())
    A, BC = X[:N], X[N + 1 :]
    cnt = [0] * (10 ** 5 + 1)
    for a in A:
        cnt[a] += 1
    total = sum(A)
    res = []
    for b, c in zip(*[iter(BC)] * 2):
        total += (c - b) * cnt[b]
        res.append(total)
        cnt[c] += cnt[b]
        cnt[b] = 0
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
rl=sys.stdin.readline
n=rl()
A=list(map(int,rl().split()))
q=int(rl())
D=Counter(A)
s=sum(A)
for _ in range(q):
  b,c=map(int,rl().split())
  s+=(c-b)*D[b]
  D[c]+=D[b]
  del D[b]
  print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
lis = list(map(int,input().split()))
l = Counter(lis)
d = [0]+[l[i+1] for i in range(10**5)]
q = int(input())
s = sum(lis)
for i in range(q):
    a,b=map(int,input().split())
    if d[a]!=0:
        temp = d[a]
        d[a]=0
        d[b]+=temp
        s += temp*(b-a)
    print(s)

Submission status: Accepted

Solution code:
# D - Replacing
from collections import defaultdict


def main():
    N, *X = map(int, open(0).read().split())
    A, BC = X[:N], X[N + 1 :]
    cnt = defaultdict(int)
    for a in A:
        cnt[a] += 1
    total = sum(A)
    res = []
    for b, c in zip(*[iter(BC)] * 2):
        total += (c - b) * cnt[b]
        res.append(total)
        cnt[c] += cnt[b]
        cnt[b] = 0
    print("\n".join(map(str, res)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter
readline=sys.stdin.readline
n=readline()
A=list(map(int,readline().split()))
q=int(readline())
D=Counter(A)
s=sum(A)
for _ in range(q):
  b,c=map(int,readline().split())
  s+=(c-b)*D[b]
  D[c]+=D[b]
  del D[b]
  print(s)

Submission status: Accepted

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    l = Counter(a)
    d = [0] + [l[i+1] for i in range(10**5)]
    Q = int(input())
    s = sum(a)
    for _ in range(Q):
        B,C = map(int,input().split())
        if d[B] != 0:
            tmp = d[B]
            d[B] = 0
            d[C] += tmp
            s = s - tmp*B + tmp*C
        print(s)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

ans = sum(a)

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

Submission status: Accepted

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

S = sum(A)
dp = [0] * 100001
for a in A:
    dp[a] += 1


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout, setrecursionlimit
from collections import deque, defaultdict, Counter
import math

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: map(int, stdin.readline().split())
rlf = lambda: map(float, stdin.readline().split())

INF, NINF = float('inf'), float('-inf')

def main():
	n = int(rl())
	A = list(rli())
	currsum = sum(A)
	F = Counter(A)
	for _ in range(int(rl())):
		b, c = rli()
		sub, add = F[b]*b, F[b]*c
		F[c] += F[b] 
		F[b] = 0
		currsum += add - sub 
		print(currsum)
		
	stdout.close()

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
count = dict()
ans = 0
for i in a:
  ans += i
  if(str(i) in count):
    count[str(i)] += 1
  else:
    count[str(i)] = 1

for i in range(q):
  b, c = input().split()
  now_n = 0
  if(b in count):
    now_n = count[b]
    count.pop(b)
    
  if(c in count):
    count[c] += now_n
  else:
    count[c] = now_n
    
  ans += now_n*(int(c) - int(b))
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
A = defaultdict(lambda:0)
B = list(map(int,input().split()))
S = sum(B)
for i in B:
    A[i] += 1
q = int(input())
for _ in range(q):
    b,c = map(int,input().split())
    if A[b] > 0:
        S += (c-b)*A[b]
        A[c] += A[b]
        A[b] = 0
    print(S)

Submission status: Accepted

Solution code:
from sys import exit
# import copy
# import numpy as np
# from collections import deque
import collections

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

count = [0]*100000
ans = 0
for i in a:
    count[i - 1] += 1
    ans += i

for que in b:
    count[que[1] - 1] += count[que[0] - 1]
    ans += (que[1]-que[0])*count[que[0] - 1]
    count[que[0] - 1] = 0
    print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())

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

Q = int(input())

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

# print(N,A,Q,B,C)


a = []

a = dict(collections.Counter(A))

s = 0
for k in a:
    s += k * a[k]
# print(s)

# sに対する増減だけ管理する

for i in range(Q):
    # 変更後
    after = {B[i]: 0, C[i]: a.setdefault(B[i], 0) + a.setdefault(C[i], 0)}
    # print(a, after)

    s = s + (C[i] - B[i] ) * a[B[i]]

    print(s)

    a.update(after)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
num=defaultdict(int)
sm=0
for e in a:
    sm+=e
    num[e]+=1
q=int(input())
for _ in range(q):
  b,c=map(int,input().split())
  ans= sm+(c-b)*num[b]
  num[c]+=num[b]
  num[b]=0
  sm=ans
  print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

def L(): 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())

import collections

def solver(N,A,Q,BC):
    T = sum(map(int,A))
    #print(T)

    Nums = collections.Counter(A)
    #print(Nums)
    for b,c in BC:
        diff = c - b

        T += Nums[b] * diff
        print(T)

        Nums[c] += Nums[b]
        Nums[b] = 0


def main():
    N = I()
    A = LI()
    Q = I()
    BC = []*Q
    BC = [LI() for _ in range(Q)]

    solver(N,A,Q,BC)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
s = [0] * (10**5+5)
Q = int(input())
total = sum(A)

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

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

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
from collections import defaultdict as dd
from math import log,ceil

def main():
    v=[0 for i in range(100001)]
    n=int(input())
    ar=list(map(int,input().split()))
    s=0
    for i in ar:
        s+=i
        v[i]+=1
    q=int(input())
    for i in range(q):
        a,b=map(int,input().split())
        s-=a*v[a]
        s+=b*v[a]
        v[b]+=v[a]
        v[a]=0
        print(s)


BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    A_dict = dict(Counter(A))
    A_sum = sum([i * j  for i, j in A_dict.items()])
    
    ans = []
    for i in range(Q):
        B, C = map(int, input().split())
        if not A_dict.get(B):
            ans.append(A_sum)
            continue
        diff = (C - B) * A_dict[B]
        A_sum += diff
        ans.append(A_sum)

        A_dict.setdefault(C, 0)
        A_dict[C] += A_dict[B]
        del A_dict[B]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
D=dict()
s=0
for i in A:
  s+=i
  if i in D:
    D[i]+=1
  else:
    D[i]=1
for _ in range(Q):
  b,c=map(int,input().split())
  if b in D:
    s+=(c-b)*D[b]
    if c in D:
      D[c]+=D[b]
    else:
      D[c]=D[b]
    del D[b]
  print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())
total = sum(a)

a = Counter(a)
for _ in range(q):
    b, c = map(int, input().split())
    total += a[b] * c
    total -= a[b] * b
    a[c] += a[b]
    del a[b]
    print(total)