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; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	A = getlist()
	Q = int(input())
	D = defaultdict(int)
	S = sum(A)
	for i in range(N):
		D[A[i]] += 1
	for i in range(Q):
		B, C = getlist()
		S += (C - B) * D[B]
		D[C] += D[B]
		D[B] = 0
		print(S)


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
n = int(input())
*a,=map(int, input().split())
from collections import defaultdict
da=defaultdict(int)
for i in a:
    da[i]+=1
q = int(input())
suma=sum(a)
for i in range(q):
    b,c=map(int, input().split())
    numb=da[b]
    suma+=(c-b)*numb
    da[c]+=numb
    da[b]=0
    print(suma)

Submission status: Accepted

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

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

D = {}
for i in range(1, 10**5+1):
    D[i] = 0

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

ret = sum(A)

for b, c in BC:
    sa = c - b
    #minus = b * D[b]
    #cnt = D[b]
    plus = sa * D[b]
    D[c] += D[b]
    D[b] = 0
    ret += plus
    print(ret)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

D=defaultdict(int)
for a in A:
    D[a]+=1

S=sum(A)

Q = int(input())

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

    m = D[b]

    D[c]+=D[b]
    D[b]=0
    diff = (c-b)*m
    S+=diff
    print(S)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    n=II()
    aa=LI()
    q=II()
    mx=10**5+5
    cnt=[0]*mx
    for a in aa:cnt[a]+=1
    s=sum(aa)
    for _ in range(q):
        b,c=MI()
        s+=(c-b)*cnt[b]
        cnt[c]+=cnt[b]
        cnt[b]=0
        print(s)

main()

Submission status: Accepted

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


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

dict = defaultdict(int)
for a in A:
    dict[a] += 1


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

Submission status: Accepted

Solution code:
N=int(input())
l=list(map(int,input().split()))
d={}
for j in range(N):
	if l[j] not in d:
		d[l[j]]=0
	d[l[j]]+=1
ans=sum(l)
Q=int(input())
for i in range(Q):
	B,C=map(int,input().split())
	if B in d:
		v=d[B]
		if C in d:
			d[C]+=d[B]
		else:
			d[C]=d[B]
		del(d[B])
		ans+=(C-B)*v
	print(ans)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, numpy, string
import sys
from bisect import bisect_left, bisect_right, insort
from collections import deque
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int, sys.stdin.readline().rstrip().split())
def MS(): return map(str, sys.stdin.readline().rstrip().split())
def LI(): return list(map(int, sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
# N = I()
# A = [LI() for _ in range(N)]


n = I()
a = LI()
box = [0] * 100000
q = I()
for i in range(n):
    box[a[i]-1] += 1
ans = 0
for i in range(len(box)):
    ans += (i+1) * box[i]

for i in range(q):
    b,c = MI()
    x = box[b-1]
    box[c-1] += x
    box[b-1] = 0
    ans += c * x - b*x
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Ali = list(map(int,input().split()))
Q = int(input())
s = 0

alin = [0]*100001#各数字の個数
for i in range(N):
  alin[Ali[i]] += 1
  s += Ali[i]
  
for i in range(Q):
  B,C = map(int,input().split())
  alin[C] += alin[B]
  s += (C-B)*alin[B]
  alin[B] = 0
  print(s)

Submission status: Accepted

Solution code:
import sys

N=int(sys.stdin.readline())

A=[int(i) for i in sys.stdin.readline().split()]

Q=int(sys.stdin.readline())

ans=sum(A)

arr=[0]*(pow(10,5)+1)

for g in range(N):
	arr[A[g]]+=1

for q in range(Q):
	[B,C]=[int(x) for x in sys.stdin.readline().split()]
	ans=ans+arr[B]*(-B+C)
	arr[C]+=arr[B]
	arr[B]=0
	print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(n) for n in input().split()]
Q = int(input())

D = dict()
for a in A:
    if a not in D.keys():
        D[a] = 0
    D[a] += 1

ans = 0
for k, v in D.items():
    ans += k * v
    
for _ in range(Q):
    B, C = [int(n) for n in input().split()]
    
    if B in D.keys():
        count = D[B]
        
        if C not in D.keys():
            D[C] = 0
        D[C] += count
        del D[B]
        
        ans += (C - B) * count

    print(ans)

Submission status: Accepted

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

sum = sum(a)

list_temp = [0 for i in range(10**5)]

for i in range(N):
    list_temp[a[i]-1] += 1

Q = int(input())
ans = [0 for i in range(Q)]

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

Submission status: Accepted

Solution code:
n=int(input())
from collections import Counter as co
g=list(map(int,input().split()))
l=co(g)
f=sum(g)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    if b in l:
        v=l[b]
        l[b]=0
        l[c]+=v
        f=f-v*b+c*v
    print(f)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
N_MAX = 200000 + 5
INF = 10**9 + 7
sys.setrecursionlimit(N_MAX)
MOD = 10**9 + 7

N = int(sys.stdin.readline())
A = [int(x) for x in sys.stdin.readline().split()]

Q = int(sys.stdin.readline())

sum = sum(A)

C = Counter(A)

for i in range(Q):
    b, c = map(int, sys.stdin.readline().split())

    # b の数を求める (=c)
    n = C[b]
    # b の合計を求める
    # sum から引く
    sum -= b * n
    C[b] = 0
    # c の合計を求める
    # sum に足す
    sum += c * n
    C[c] += n
    print(sum)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    arr = list(map(int,input().split()))
    nums = {}
    for i in arr:
        if i not in nums.keys():
            nums[i] = 0

        nums[i] += 1

    total = sum(arr)
    ans = []
    q = int(input())
    for i in range(q):
        b,c = map(int,input().split())
        if b in nums.keys():
            total -= b*nums[b]
            total += c*nums[b]
            count = nums[b]
            del nums[b]
            if c not in nums.keys():
                nums[c] = 0

            nums[c] += count
            
        ans.append(total)

    for i in ans:
        print(i)

main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

counter = collections.Counter(al)

total = 0
for (v, c) in counter.most_common():
  total += v * c
for _ in range(q):
  b, c = [int(i) for i in input().split()]
  count = counter[b]
  counter[b] = 0
  counter[c] += count
  total = total + (c - b) * count
  print(total)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()
    
input()
A = input().split(' ')
A = list(map(int, A))
Q = int(input())

curr_sum = sum(A)
curr_freqs = dict()

for a in A:
    if a not in curr_freqs: curr_freqs[a] = 0
    curr_freqs[a] += 1

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

    if B not in curr_freqs:
        print(curr_sum)
        continue

    if C not in curr_freqs: curr_freqs[C] = 0

    curr_sum += (C - B)*curr_freqs[B]

    curr_freqs[C] += curr_freqs[B]
    curr_freqs[B] = 0


    print(curr_sum)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
X = [0]*(100001)
S = 0
for a in A:
    X[a] += 1
    S += a

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LFR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
def LIR_(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def SR(n):
    res = [None] * n
    for i in range(n):
        res[i] = S()
    return res
def LSR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LS()
    return res
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    a = LI()
    q = II()
    bc = LIR(q)
    d = defaultdict(int)
    for i in a:
        d[i] += 1
    ans = 0
    for key, value in d.items():
        ans += key * value 
    for b, c in bc:
        x = d[b]
        ans -= x * b
        d[b] = 0
        d[c] += x
        ans += x * c
        print(ans)
    return


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

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
from decimal import *
import heapq
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
q = INT()
arr = [0 for _ in range(10 ** 5 + 100)]
for i in a:
    arr[i] += 1
ans = sum(a)
for _ in range(q):
    b, c = MAP()
    arr[c] += arr[b]
    ans += (c - b) * arr[b]
    arr[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    l = Counter(A)
    # print(l)
    Q = int(input())
    ans = sum(A)
    
    for i in range(Q):
        B, C = map(int, input().split())
        tmp = l[B]
        l[C]+=tmp
        l[B] = 0
        ans += (C-B)*tmp
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

lst=[0]*(10**5+1)
ans=0
for i in range(n):
    lst[a[i]]+=1
    ans+=a[i]
# print(ans)

for i in range(q):
    b,c=bc[i]
    bcnt=lst[b]
    ans+=(c-b)*bcnt
    lst[c]+=bcnt
    lst[b]=0
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]

f = Counter()

for x in a:
    f[x] += 1

ans = 0
for x, val in f.items():
    ans += x*val

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()
A_array = na()
a_dic = {}

ans = 0
for a in A_array:
    ans += a
    if a in a_dic:
        a_dic[a] += 1
    else:
        a_dic[a] = 1

ans_array = []

Q = ni()
for _ in range(Q):
    b, c = na()
    if b in a_dic:
        if c in a_dic:
            a_dic[c] += a_dic[b]
        else:
            a_dic[c] = a_dic[b]
        ans = ans + (c - b) * a_dic[b]
        a_dic[b] = 0
    ans_array.append(ans)

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

Submission status: Accepted

Solution code:
import math
import time
from collections import defaultdict,deque
from sys import stdin,stdout
from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,stdin.readline().split()))
q=int(input())
count=defaultdict(lambda:0)
for i in a:
    count[i]+=1
s=sum(a)
for _ in range(q):
    b,c=map(int,stdin.readline().split())
    s+=count[b]*(c-b)
    count[c]+=count[b]
    count[b]=0
    print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s = sum(a)
d = defaultdict(int)
for ai in a:
    d[ai] += 1

for xi in x:
    b, c = xi
    s += d[b] * (c - b)
    print(s)
    d[c] += d[b]
    d[b] = 0

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
BC = []
B = 0
C = 1
for i in range(q):
   BC.append(list(map(int, input().split())))

cnt = [0] * (10**5 + 1)
S = sum(a)

for _a in a:
    cnt[_a] += 1

for bc in BC:
    bCount = cnt[bc[B]]
    cnt[bc[B]] = 0
    cnt[bc[C]] += bCount
    S += (bc[C] - bc[B])*bCount
    print(S)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

cnt = Counter(As)
ans = sum(As)

anss = []
for B, C in BCs:
    num = cnt[B]
    diff = num * (C-B)
    ans += diff
    anss.append(ans)
    cnt[B] -= num
    cnt[C] += num

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

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 = Counter(A)
    for b, c in zip(BC[::2], BC[1::2]):
        total -= b * d[b]
        total += c * d[b]
        d[c] += d[b]
        d[b] = 0
        print(total)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A_list = list(map(int, input().split()))
A_dict = {}
res = 0
for a in A_list:
    res += a
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

Q = int(input())
for i in range(Q):
    b,c = map(int, input().split())
    tmp = A_dict[b] if b in A_dict.keys() else 0
    A_dict[b] = 0

    if c in A_dict.keys():
        A_dict[c] += tmp
    else:
        A_dict[c] = tmp

    res += c*tmp - b*tmp
    print(res)

Submission status: Accepted

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

n = int(input())
a = [int(x) for x in input().split()]
chk = [0] * 100001
now = sum(a)

for x in a:
    chk[x] += 1

for _ in range(int(input())):
    b, c = map(int, input().split())
    now = now - chk[b] * b + chk[b] * c
    chk[c] += chk[b]
    chk[b] = 0

    print(now)

Submission status: Accepted

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

total = sum(A_list)

table = {}
for A in A_list:
	if A in table:
		table[A] += 1
	else:
		table[A] = 1

Q = int(input())
for _ in range(Q):
	B, C = map(int, input().split())
	if B in table:
		count = table[B]
		total -= count * B
		total += count * C
		if C in table:
			table[C] += count
		else:
			table[C] = count
		del table[B]
	print(total)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
*a, = map(int,readline().split())
q,*bc = map(int,read().split())

from collections import Counter
d = Counter(a)
res = sum(a)


m = iter(bc)
for b,c in zip(m,m):
    if b in d:
        v = d[b]
        d[b] = 0
        d[c] += v
        res += (c-b)*v
    print(res)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
A = tuple(map(int, readline().split()))
Q = int(readline())
m = map(int, read().split())

counter = defaultdict(int)
for x in A:
    counter[x] += 1

total = sum(A)
for b, c in zip(m, m):
    total += (c - b) * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(total)

Submission status: Accepted

Solution code:
n = int(input())

aa=list(map(int,input().split()))
q = int(input())
b=[]
c=[]
from collections import Counter as cnt
ans = sum(aa)

a = dict(cnt(aa))
for i in range(q):
    bb,cc=list(map(int,input().split()))
    b.append(bb)
    c.append(cc)
    if bb not in a:
        a[bb]=0
    if cc not in a:
        a[cc]=0



for i in range(q):
    ans += a[b[i]]*(c[i]-b[i])
    a[c[i]] += a[b[i]]

    a[b[i]] = 0
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
val = [0]*(10**5)
for a in A:
    val[a-1] += 1

t = 0
for i,n in enumerate(val):
    t += (i + 1)*n

ans = []
Q = int(input())
for _ in range(Q):
    B,C = [int(i) for i in input().split()]
    t += (C - B)*val[B-1]
    val[C-1] += val[B-1]
    val[B-1] = 0
    ans.append(str(t))
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
def solve(n, a_list, q, bc_list):
    v_list = [0] * (10 ** 5 + 1)
    s = 0
    for i in range(n):
        a = a_list[i]
        v_list[a] += 1
        s += a
    res_list = []
    for i in range(q):
        b, c = bc_list[i]
        s += v_list[b] * (c - b)
        v_list[c] += v_list[b]
        v_list[b] = 0
        res_list.append(s)
    return res_list


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    q = int(input())
    bc_list = [list(map(int, input().split())) for _ in range(q)]
    res = solve(n, a_list, q, bc_list)
    for r in res:
        print(r)


def test():
    assert solve(4, [1, 2, 3, 4], 3, [[1, 2], [3, 4], [2, 4]]) == [11, 12, 16]
    assert solve(4, [1, 1, 1, 1], 3, [[1, 2], [2, 1], [3, 5]]) == [8, 4, 4]
    assert solve(2, [1, 2], 3, [[1, 100], [2, 100], [100, 1000]]) == [102, 200, 2000]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys

input = sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))

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

for a in A:
    C[a] += 1
Q = int(input())

res = sum(A)
for _ in range(Q):
    b,c = map(int, input().split())
    res += (c-b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(res)

Submission status: Accepted

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

Submission status: Accepted

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

cnt = [0 for _ in range(101010)]

ans = 0
for x in a:
    cnt[x] += 1
    ans += x

q = int(input())

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

Submission status: Accepted

Solution code:
#coding: utf-8
N = int(input())
A = list(map(int,input().split()))
Q = int(input())

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_a_int(): return int(read())


def read_ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

N = read_a_int()
A = read_ints()
Q = read_a_int()
B, C = read_col(Q)

# 各数が何回登場するかカウントすれば良い
cnt = Counter(A)
ans = []
tmp = sum(A)
for b, c in zip(B, C):
    # 値がBであるものの個数の取得と0に書き換え
    n = cnt[b]
    cnt[b] = 0
    # 値cへの加算
    cnt[c] += n
    tmp -= n * b
    tmp += n * c
    ans.append(tmp)


# ans = 0
# for k, v in cnt.items():
#     ans += k * v
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# itne me hi thakk gaye?
from collections import defaultdict
n = int(input())
mp = defaultdict(int)
arr = list(map(int, input().split()))
cur_sum = 0
for i in arr:
    cur_sum += i
    mp[i] += 1
for i in range(int(input())):
    a, b = map(int, input().split())
    fra = mp[a]
    cur_sum -= a*fra
    mp[a] -= fra
    mp[b] += fra
    cur_sum += b*fra
    print(cur_sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase

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

def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7


Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

n = int(ri())
a = Ri()

m = int(ri())
summ = sum(a)
dic = {}
for i in a:
    dic[i] = dic.get(i,0 )+1

for _ in range(m):
    l,r = Ri()
    if l in dic:
        cnt = dic[l]
        summ -= cnt*l
        summ += cnt*r

        dic.pop(l)
        dic[r] = dic.get(r, 0) + cnt
    print(summ)

Submission status: Accepted

Solution code:
from collections import Counter

(N,) = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
(Q,) = [int(x) for x in input().split()]
BC = [[int(x) for x in input().split()] for i in range(Q)]

freq = Counter(A)
total = sum(A)
for B, C in BC:
    total += (C - B) * freq[B]
    freq[C] += freq[B]
    del freq[B]
    print(total)

Submission status: Accepted

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