Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

l = [[i, 0] for i in range(10**5+1)]
for _ in range(n):
    l[A[_]][1] += 1
#print(l)

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

Submission status: Accepted

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

dp=[0 for i in range(1,10**6)]
for i in A:
    dp[i]+=1
S=sum(A)
for i in B:
    S+=(i[1]-i[0])*dp[i[0]]
    print(S)
    dp[i[1]]+=dp[i[0]]
    dp[i[0]]=0

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
X = Counter(a)
q = int(input())
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
for i in range(q):
    b[i], c[i] = map(int, input().split())

ans = sum(a)
for num, rep in zip(b, c):
    ans += (rep * X[num] - num * X[num])
    X[rep] += X[num]
    del(X[num])
    print(ans)

Submission status: Accepted

Solution code:
import collections

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

Submission status: Accepted

Solution code:
k = [i for i in range(1, 10 ** 5 + 1)]
v = [0] * (10 ** 5)
dic = {key: val for key, val in zip(k, v)}
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
  dic[a[i]] += 1
q = int(input())
ans = [sum(a)]
for i in range(q):
  b, c = map(int, input().split())
  ans.append(ans[-1] + (c - b) * dic[b])
  dic[c] += dic[b]
  dic[b] = 0
for i in range(1, q + 1):
  print(ans[i])

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
count = [0 for _ in range(int(1e5)+1)]
for a in A:
    count[a] += 1    

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
a = Counter(map(int, input().split()))
Q = int(input())

sum_a = sum(a.elements())

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

Submission status: Accepted

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

from collections import defaultdict
dic = defaultdict(int)

ans = 0
for a in al:
    dic[a] += 1
    ans += a


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

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
freq={}
for i in range(n):
	freq[l[i]]=0
for i in range(n):
	freq[l[i]]+=1
t=int(input())
sm=sum(l)
for i in range(t):
	a,b=map(int,input().split())
	if(a not in freq.keys()):
		print(sm)
	else:
		if(b not in freq.keys()):
			freq[b]=0
		#diff=abs(freq[b]-freq[a])
		sm=sm-a*freq[a]+b*freq[a]
		freq[b]+=freq[a]
		freq[a]=0
		print(sm)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
from collections import defaultdict
R = defaultdict(int)
for a in A:
    R[a] += 1
Q = int(input())
for i in range(Q):
    b,c = map(int,input().split())
    cnt = R[b]
    del R[b]
    R[c] += cnt
    if i == 0:
        ans = 0
        for key in R.keys():
            ans += (R[key]*key)
        print(ans)
    else:
        ans = ans - cnt*b + cnt*c
        print(ans)

Submission status: Accepted

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

l = [0] * 100001

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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

N = I()
A = LI()
Q = I()
B,C = LIR(Q,2)

ans = []
d = defaultdict(int)
for i in range(N):
    d[A[i]] += 1

sum_ = sum(A)
for i in range(Q):
    num = d[B[i]]
    sum_ = sum_+num*(C[i]-B[i])
    ans.append(sum_)
    d[B[i]] -= num
    d[C[i]] += num

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
dic = {}
for i in A:
    if i in dic:
        dic[i] = dic[i]+1
    else :
        dic[i] = 1
s = sum(A)

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

for b,c in zip(B,C):
    if b in dic:
        temp = dic[b]
        s = s + (c-b)*temp
        del dic[b]
        if c in dic:
            dic[c] = dic[c]+temp
        else :
            dic[c] = temp
    print(s)

Submission status: Accepted

Solution code:
s = int(input()) 

dict={}
num_list = list(map(int, input().split()))

length=len(num_list)
count=[0]*(s+1000)
for i in range(length):
    count[num_list[i]]+=1
    dict[num_list[i]]=count[num_list[i]]
    
sum=0
#print(dict)
for k, v in dict.items():
    sum+=k*v
#print(dict)
#print(sum)

count=0
d=0
n = int(input()) 
for i in range(n):
    a,b = map(int, input().split())  
    if dict.get(a)!=None:
        d=(b-a)*dict[a]
        #print("d:{}".format(d))
        if dict.get(b)!=None:
            count=dict[b]
            dict[b]=dict[a]+dict[b]
        else:
            dict[b]=dict[a]
        dict[a]=0
        sum+=d
        
        #print(dict)
        
    else:
        pass
    d=0
    print(sum)
    #print()

Submission status: Accepted

Solution code:
import sys
def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0 for i in range(10**5+1)]
    sa = sum(a)
    for i in a:
        s[i] += 1
    q = int(input())
    for x in sys.stdin.readlines():
        b, c = map(int, x.split())
        s[c] += s[b]
        sa += (c-b)*s[b]
        s[b] = 0
        print(sa)

main()

Submission status: Accepted

Solution code:
import collections

N=int(input())
A=[int(_) for _ in input().split(" ")]
Q=int(input())

c = collections.Counter(A)

ans=0
for v in c:
  ans += v*c[v]

#print(c)
#d['k10'] = d.pop('k1')    
    
for i in range(Q):
  B,C=map(int,input().split(" "))
  
  if C in c:
    ans=ans-B*c[B]+C*c[B]
    c[C] += c[B]
    del c[B]
  else:
    ans=ans-B*c[B]+C*c[B]
    c[C] = c[B]
    del c[B]
  
  print(ans)

Submission status: Accepted

Solution code:
import sys
def main():
    n = int(input())
    a = list(map(int, input().split()))
    s = [0 for i in range(10**5+1)]
    sa = sum(a)
    for i in a:
        s[i] += 1
    q = int(input())
    for x in sys.stdin.readlines():
        b, c = map(int, x.split())
        s[c] += s[b]
        sa = sa + (c-b)*s[b]
        s[b] = 0
        print(sa)

main()

Submission status: Accepted

Solution code:
N = int(input())
AList = list(map(int, input().split()))
Q = int(input())
dp = [0]*(10**5+1)
total = 0
for i in AList:
  dp[i] += 1
  total += i
  
for i in range(Q):
  B,C = map(int, input().split())
  bNum = dp[B]
  dp[B] = 0
  dp[C] += bNum
  cNum = dp[C]
  total = total - B*bNum + C*bNum
  print(total)

Submission status: Accepted

Solution code:
import sys

def I(): 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 main():
    n = I()
    a = LI()
    q = I()
    b = [0]*q
    c = [0]*q
    for i in range(q):
        b[i], c[i] = MI()
    a_num = [0]*100001
    for ai in a:
        a_num[ai] += 1
    a_sum = sum(a)
    for i in range(q):
        a_sum += (c[i]-b[i])*a_num[b[i]]
        a_num[c[i]] += a_num[b[i]]
        a_num[b[i]] = 0
        print(a_sum)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int,input().split()))
#print(a)
q = int(input())
z = [0 for i in range(100001)]
for i in range(len(a)):
    z[a[i]] += 1
x = sum(a)
b = []
for _ in range(q):
    b.append(list(map(int,input().split())))
#print(b)


for i in range(q):
    x += (b[i][1] - b[i][0]) * z[b[i][0]]
    z[b[i][1]] += z[b[i][0]]
    z[b[i][0]] = 0
    print(x)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
B = [[int(i) for i in input().split()] for Q in range(Q)]

p = [0]*100001
for i in range(N):
    p[A[i]] += 1

cnt = 0
for j in range(100001):
    cnt += p[j]*j

for i in range(Q):
    cnt = cnt + (B[i][1]- B[i][0]) * p[B[i][0]]

    p[B[i][1]] += p[B[i][0]]
    p[B[i][0]] = 0

    print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

num_A = [0 for i in range(10**5+1)]
first = 0

for a in A:
    num_A[a] += 1
    first += a

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

Submission status: Accepted

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

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

sum = 0
for i in range(0, 1):
    b = B[i]
    c = C[i]
    if b in A_new:
        n = A_new[b]
        A_new[b] = 0
        if c in A_new:
            A_new[c] += n
        else:
            A_new[c] = n
    key_list = A_new.keys()
    res = 0
    for k in key_list:
        res += A_new[k] * k
    print(res)
    sum = res


for i in range(1, Q):
    b = B[i]
    c = C[i]
    dif = 0
    if b in A_new:
        n = A_new[b]
        A_new[b] = 0
        if c in A_new:
            A_new[c] += n
        else:
            A_new[c] = n
        dif = c * n - b * n
    sum += dif
    print(sum)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
L = []
for i in range(Q):
    B,C = map(int,input().split())
    L.append([B,C])
c = {}
for i in range(1,100001):
    c[i] = 0
for k in A:
    c[k] += 1
s = sum(A)
for i in range(Q):
    if c[L[i][0]] == 0:
        print(s)
    else:
        n = c[L[i][0]]
        c[L[i][1]] += n
        c[L[i][0]] = 0
        s += (L[i][1] - L[i][0])*n
        print(s)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from collections import Counter

n = ii()
A = iil()
s = sum(A)
d = Counter(A)

q = ii()

for i in range(q):
    b,c = iim()
    m = d.pop(b,0)
    d[c] = d.get(c,0)+m
    s += (c-b)*m
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter


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

    C = Counter(A)
    ANS = 0
    for i in C:
        ANS += i * C[i]

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

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

resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
li = [0]*100001
for a in A:
    li[a] += 1
ans = sum(A)
# print(dict_A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b)*li[b]
    li[c] += li[b]
    li[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans, dic = 0, {i:0 for i in range(1, 10**5 + 1)}
for a in A:
    ans += a
    dic[a] += 1
Q = int(input())

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()
d = defaultdict(int)
ans = sum(A)
for a in A:
    d[a] += 1

Q = I()
for q in range(Q):
    B, C = MI()
    ans -= B * d[B]
    ans += C * d[B]
    d[C] += d[B]
    d[B] = 0
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
li = [0]*100001
for a in A:
    li[a] += 1
ans = sum(A)
# print(dict_A)
for i in range(Q):
    b, c = map(int, input().split())
    ans += (c-b)*li[b]
    li[c] += li[b]
    li[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys

def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり

from collections import Counter

N = I()
A = LI()
sum = sum(A)
a = Counter(A)

Q = I()
for i in range(Q):
    b,c = LI()
    sum += a[b]*(c-b)
    print(sum)
    a[c] += a[b]
    a[b] = 0

Submission status: Accepted

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

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

ans = sum(A)

for j in range(Q):
    b, c = map(int, input().split())
    a = X[b-1]
    X[b-1] = 0
    X[c-1] += a
    ans = ans - a*b + c*a
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import collections

n = int(input())
a =np.array([int(x) for x in input().split()])
q = int(input())
bc = [map(int, input().split()) for _ in range(q)]
b, c = [list(i) for i in zip(*bc)]

count_dict = collections.Counter(a)
ans = np.sum(a)
for i in range(q):
    if count_dict[b[i]] > 0:
        ans += count_dict[b[i]]*(c[i]-b[i])
        count_dict[c[i]] += count_dict[b[i]]
        count_dict[b[i]] = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
LOCAL = len(sys.argv) > 1 and sys.argv[1] == 'LOCAL'


def dprint(*args):
  if LOCAL:
    print(*args)


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

import collections

buk = [0] * (10**5 + 1)
for e in a:
  buk[e] += 1

s = sum(a)

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

Submission status: Accepted

Solution code:
n = int(input())
*a, = map(int,input().split())
M = 10**5+1
g = [0] * M
s = 0
for A in a:
    g[A] += 1
    s += A

q = int(input())
for loop in range(q):
    b,c = map(int,input().split())
    if g[b] == 0:
        print(s)
        continue
    s += g[b] * (c - b)
    g[c] += g[b]
    g[b] = 0
    print(s)

Submission status: Accepted

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

cnt = [0]*100001
for c in a:
    cnt[c] += 1

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

Submission status: Accepted

Solution code:
def main():
    import sys
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
    sys.setrecursionlimit(10 ** 7)

    from collections import Counter

    n = int(readline())
    a = list(map(int, readline().split()))
    ans = sum(a)
    counter = Counter(a)
    q = int(readline())
    for _ in range(q):
        b, c = map(int, readline().split())
        ans += (c - b) * counter[b]
        counter[c] += counter[b]
        counter[b] = 0
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
M = 100002

if __name__ == "__main__":
  N = int(input())
  A = [int(x) for x in input().split()]
  Q = int(input())
  Num = np.zeros((M))
  Sum = sum(A)
  for i in range(N):
    Num[A[i]] += 1
  for i in range(Q):
    B, C = [int(x) for x in input().split()]
    if(Num[B] == 0):
      print(int(Sum))
    else:
      Sum = Sum + (C - B)*Num[B]
      Num[C] += Num[B]
      Num[B] = 0
      print(int(Sum))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    N=int(input())
    l=[0]*10**5
    sm=0
    A=map(int, input().split())
    for a in A:
        l[a-1]+=1
        sm+=a
    Q=int(input())
    BC=[list(map(int,input().split())) for _ in range(Q)]
    for bc in BC:
        cnt=l[bc[0]-1]
        l[bc[0]-1]=0
        l[bc[1]-1]+=cnt
        sm=sm-bc[0]*cnt+bc[1]*cnt
        print(sm)
    return

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q

num = [0]*100000

for i in range(N):
    num[A[i]-1] += 1

sum = sum(A)

for i in range(Q):
    B[i], C[i] = map(int, input().split())
    
    sum += (C[i]-B[i])*num[B[i]-1]
    num[C[i]-1] += num[B[i]-1] 
    num[B[i]-1] = 0

    print(sum)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
a=[0]*(10**5+1)
num=0
for i in range(N):
    s=A[i]
    a[s]+=1
    num+=s
Q=int(input())
ans=[]
for i in range(Q):
    B,C=map(int,input().split())
    a[C]+=a[B]
    num+=(C-B)*a[B]
    a[B]=0
    ans.append(num)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import collections
n = int(input())
li = list(map(int,input().split()))
q = int(input())
num_li=[list(map(int,input().split())) for i in range(q)]

c = collections.Counter(li)

li_sum = sum(li)

for i,j in num_li:
    s = 0
    if i in c:
        cnt = c.pop(i)
        c[j] += cnt
        li_sum = li_sum - (i*cnt) + (j*cnt)
    print(li_sum)

Submission status: Accepted

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

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

total = sum(a)

bucket = Counter()

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

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

Submission status: Accepted

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

dic = {}
for num in A:
    if num in dic:
        dic[num] += 1
    else:
        dic[num] = 1

prev_sum = 0

for key, value in dic.items():
    prev_sum += key * value

for _ in range(Q):
    B, C = map(int, input().split())
    if B in dic and C in dic:
        dic[C] += dic[B]
        dif = (C - B) * dic[B]
        prev_sum += dif
        del dic[B]
    elif B in dic and C not in dic:
        dic[C] = dic[B]
        dif = (C - B) * dic[B]
        prev_sum += dif
        del dic[B]
    print(prev_sum)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

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

Q = int(input())
for _ in range(Q):
    x, y = map(int, input().split())
    S += (c[x]*(y-x))
    print(S)
    c[y] += c[x]
    c[x] = 0

Submission status: Accepted

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

data = [0] * 100001

def my_sum(d):
    retval = 0

    for i in range(len(d)):
        if d[i] == 0:
            continue
        retval += d[i] * i
    return retval

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

sum_val = my_sum(data)

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

    sum_val = sum_val - (data[B] * B) + (data[B] * C)

    data[C] += data[B]
    data[B] = 0

    print(sum_val)

Submission status: Accepted

Solution code:
from collections import Counter

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 = Counter(A)
ans = 0
for num, count in counter.items():
    ans += num * count

for i in range(Q):
    if B[i] in counter:
        ans += counter[B[i]] * C[i] - counter[B[i]] * B[i]
        counter[C[i]] = counter[C[i]] + counter.pop(B[i])
    print(ans)

Submission status: Accepted

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

sum = 0
for i in range(N):
    sum += A[i]
dic = cl.Counter(A)

l = []
for _ in range(Q):
    b, c = map(int, input().split())
    x = dic.get(b)
    if x == None:
        l.append(sum)
        continue
    if b < c:
        sum += (c - b) * x
    else:
        sum -= (b - c) * x
    l.append(sum)
    if c not in dic:
        dic[c] = dic.pop(b)
    else:
        dic[c] = dic.pop(b) + dic[c]

for s in l:
    print(s)

Submission status: Accepted

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

bs = []
cs = []
for i in range(q):
  b,c = map(int, input().split())
  bs.append(b)
  cs.append(c)

total = sum(a)
a = Counter(a)  

for i in range(q):
  dif = cs[i] - bs[i]
  total += dif * a[bs[i]]
  a[cs[i]] += a[bs[i]]
  a[bs[i]] = 0
  print(total)

Submission status: Accepted

Solution code:
n = int(input())
table = [0 for i in range(100000)]

a = list(map(int, input().split()))
s = sum(a)

for e in a:
    table[e-1] += 1

q = int(input())

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

Submission status: Accepted

Solution code:
# # ####################################################################
# import io
# import sys

# _INPUT = """\
# 1
# 10
# 3
# 10 1
# 1 2
# 3 1
# """
# sys.stdin = io.StringIO(_INPUT)
####################################################################


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

from collections import Counter
C = Counter(A)

sumA = sum(A)

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

  k = C[b]

  # if b==c:
  #   print(sumA)
  #   continue

  # if d[b] == 0:
  #   print(sumA)
  #   continue

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

  C[c] += k
  C[b] = 0

Submission status: Accepted

Solution code:
#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B = [0] * Q
    C = [0] * Q
    for i in range(Q):
        B[i], C[i] = map(int, input().split())
        
    #output
    from collections import Counter
    D = Counter(A)
    S = sum(A)

    for i in range(Q):
        x = D[B[i]]
        temp = S - x*B[i] + x*C[i] 
        print(temp)
        D[B[i]] = 0
        D[C[i]] += x
        S = temp    

    #N = 1のときなどcorner caseを確認！
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())
ans = sum(A)
C = Counter(A)

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

Submission status: Accepted

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

num = [0]*(10**5+1)

sum = sum(A)
for i in range(N):
  num[A[i]-1] += 1

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

Submission status: Accepted

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

at = [0]*(10**5+100)
sum = 0

for i in a:
    at[i]= at[i]+1
    sum = sum+i


for  i in range(q):
    m= at[b[i]]
    at[b[i]]=0
    at[c[i]]=at[c[i]]+m

    sum = sum + (c[i]-b[i])*m
    print(sum)

Submission status: Accepted

Solution code:

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

max_num = max(max(A), max(B), max(C))

NUM = [0] * (max_num + 1)

num_list = []

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

total = sum(A)

for i in range(Q):

    total += (C[i] - B[i]) * NUM[B[i]]
    NUM[B[i]], NUM[C[i]] = 0, NUM[B[i]] + NUM[C[i]]

    print(total)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

ans=sum(a)

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


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

Submission status: Accepted

Solution code:

def main():
    import collections

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

    summ = sum(A_s)
    CNT_A = collections.Counter(A_s)


    for i in range(Q):
        before, after = map(int, input().split())
        
        tmp_cnt = CNT_A[before]
        
        if (tmp_cnt > 0):
            tmp_before = CNT_A[before] * (after - before)
            summ += tmp_before

            N_before=CNT_A[before]

            del CNT_A[before]
            N_after = CNT_A[after]
            
            if (N_after > 0):
                CNT_A[after] = N_after + N_before
            else:
                CNT_A[after] = N_before
            
        
        print(summ)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

  mem = {}
  for a in A:
    if not(a in mem):
      mem[a] = 0
    mem[a] += 1

  sum_ = sum(A)
  for i in range(Q):
    from_, to_ = map_[i]
    if not(from_ in mem):
      print(sum_)
      continue
    idiff = mem[from_]
    if not(to_ in mem):
      mem[to_] = 0
    mem[to_] += mem[from_]
    mem[from_] = 0
    diff = idiff * (to_ - from_)
    sum_ += diff
    # print(mem)
    print(sum_)


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

Submission status: Accepted

Solution code:
n=int(input())
elements= input().split()
q=int(input())
actions=[]
for i in range(q):
    actions.append(input().split())
 
dict={}
for e in elements:
    count=dict.get(e,0)
    count+=1
    dict[e]=count
 
sum=0
for key in dict.keys():
    sum+=int(key)* dict[key]

for act in actions:
    count=dict.get(act[0],0)
    sum+=(int(act[1])-int(act[0]))*count
    count+=dict.get(act[1],0)
    dict[act[1]]=count
    dict[act[0]]=0
 
    print(str(sum))

Submission status: Accepted

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

from collections import defaultdict
count = defaultdict(int)

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

ans = sum(A)

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

Submission status: Accepted

Solution code:
from sys import stdin

mapping = [0] * 100001

def main():
    n = int(input())
    a = [int(x) for x in stdin.readline().rstrip().split()]
    base = sum(a)
    for aaa in a:
        mapping[aaa] += 1
    q = int(input())
    for i in range(q):
        b, c = [int(x) for x in stdin.readline().rstrip().split()]
        offset = c - b
        kazu = mapping[b]
        base = base + kazu*offset
        mapping[b] = 0
        mapping[c] += kazu
        
        print(base)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
Q=int(input())
B=[list(map(int, input().split())) for _ in range(Q)]
D={}
ma=0
for i in A:
  ma+=i
  if i not in D:
    D[i]=1
  else:
    D[i]+=1
    
for b,c in B:
  if b in D:
    f=D[b]
    if c in D:
      t=D[c]
    else:
      t=0
    
    D[c]=f+t
    D[b]=0
    ma+=(c-b)*f
  print(ma)