Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

Solution code:
from collections import Counter

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

counted = Counter(numbers)
sum_n = sum(numbers)

for _ in range(Q):
    b, c = [int(i) for i in input().split()]
    sum_n = sum_n - ((b-c) * counted[b])
    counted[c] += counted[b]
    counted[b] -= counted[b]
    print(sum_n)

Submission status: Accepted

Solution code:
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
a = list(map(int, input().split()))
q = int(input())
req = [list(map(int, input().split())) for _ in range(q)]
count = [0]*100001
sum = sum(a)

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

for k in range(q):
    sum += (req[k][1] - req[k][0]) * count[req[k][0]]
    count[req[k][1]] += count[req[k][0]]
    count[req[k][0]] = 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())

s = 0
L = [0]*(10**5+1)
for A in a:
	L[A] += 1
	s += A

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

Submission status: Accepted

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

d=[0]*100001
for i in a:
    d[i]+=1

ans=sum(a)
for m,p in zip(b,c):
    minus=d[m]
    d[m]=0
    d[p]+=minus
    ans+=(p-m)*minus
    print(ans)

Submission status: Accepted

Solution code:
#ABC 171 D - Replacing 18:36

def func(x,y): #x -> y, xの要素数を返す
    if x not in d:
        v = 0
    else:
        v = d[x]
        if y not in d:
            d[y] = 0
            d[y] = d[x]
            del d[x]
        else:
            d[y] += d[x]
            del d[x]
    return v

n = int(input())
a = list(map(int, input().split()))
d = {}
for key in a:
    if key not in d:
        d[key] = 0
    d[key] += 1

q = int(input())
sum_a = sum(a)
for i in range(q):
    b,c = map(int, input().split())
    v = func(b,c)
    sum_a += (c-b)*v 
    print(sum_a)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = [0] * (100001)
s = sum(A)
for a in A:
    L[a] += 1
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    L[C] += L[B]
    s += L[B] * (C-B)
    L[B] = 0
    print(s)

Submission status: Accepted

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

for ai in a:
  if a_dict.get(ai):
    a_dict[ai] += 1
  else:
    a_dict[ai] = 1

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

Submission status: Accepted

Solution code:
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = defaultdict(int)
    total = 0
    for a in A:
        cnt[a] += 1
        total += a
    Q = int(input())
    for _ in range(Q):
        b, c = map(int, input().split())
        cnt[c] += cnt[b]
        total += (c-b) * cnt[b]
        cnt[b] = 0
        print(total)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

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

Q = int(input())

c = collections.Counter(a)

for i in range(Q):
    arr = list(map(int,input().split()))
    B = arr[0]
    C = arr[1]

    if(C not in c):
        c[C] = 0

    num_B = c[B] # 配列に含まれるBの個数
    c[B] = 0
    c[C] += num_B
    # c[C] += c[B]
    # del c[B]

    # for key, cnt in c.items():
    #     sum -= items():
    #     sum += key*cnt

    su -= num_B * B # bのやつを減らす
    su += num_B * C # cのやつを増やすitems():

    print(su)

Submission status: Accepted

Solution code:
from collections import Counter

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

q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    num_b = cA[b]
    if num_b > 0:
        cA[b] = 0
        cA[c] += num_b
        S += num_b * (c - b)
    print(S)

Submission status: Accepted

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


counter = [0] * 1000000
for i in a:
    counter[i] += 1
 
ans = sum(a)
 
for _ in p:
    ans = ans + counter[_[0]] * _[1] - counter[_[0]] * _[0]
    counter[_[1]] += counter[_[0]]
    counter[_[0]] = 0
    print(ans)

Submission status: Accepted

Solution code:
import math
import collections
import fractions
import itertools

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    sushi = sum(a)
    coll = collections.Counter(a)
    for _ in range(q):
        bef, aft = map(int, input().split())
        sushi += (aft-bef)*coll[bef]
        coll[aft] += coll[bef]
        coll[bef] = 0
        print(sushi)
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

n = int(input())
A = list(map(int,input().split()))
q = int(input())
M=[list(map(int,input().split())) for _ in range(q)]
Sum = sum(A)
d={}

for i in range(n):
    if A[i] not in d:
        d[A[i]]=1
    else:
        d[A[i]]+=1

for i in M:
    prev = 0
    a,b=i[0],i[1]
    if a not in d:
        print(Sum)
        continue
    
    elif b in d:
        prev = d[b]*b
        d[b]+=d[a]
    else:
        d[b]=d[a]
    
    Sum += d[b]*b-d[a]*a-prev

    d.pop(a)
    print(Sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    D = Counter(A)
    res = sum(A)
    for b, c in query:
        if D.get(b) is not None:
            res -= b * D.get(b)
            res += c * D.get(b)

        if D.get(c) is not None:
            D[c] += D[b]
        else:
            D[c] = D[b]
        D[b] = 0

        print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
import bisect

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

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

for i in range(len(A)):
    DP[A[i]] += 1

Sum = sum(A)

for i in range(Q):
    Sum += (C[i]-B[i])*DP[B[i]]
    DP[C[i]] += DP[B[i]]
    DP[B[i]] = 0
    print(Sum)

Submission status: Accepted

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

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

d = dict()
for num in S:
    d.setdefault(num, 0)
    d[num] += 1


ans = sum(s*t for s, t in d.items())

for _ in range(Q):
    b, c = map(int, input().split())
    d.setdefault(c, 0)
    d.setdefault(b, 0)
    ans += (c-b)*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()))
s = sum(a)
#print(ans)
q = int(input())
import collections
cc = collections.Counter(a)
#print(cc)
for i in range(q):
    b,c = map(int,input().split())
    tmp = cc[b]
    cc[b] = 0
    s=s-b*tmp+c*tmp
    cc[c]+=tmp
    print(s)

Submission status: Accepted

Solution code:
import collections

n=int(input())
a=list(map(int,input().split()))
q=int(input())
s=sum(a)
cc=collections.Counter(a)


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

Submission status: Accepted

Solution code:
import collections

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

c=collections.Counter(a)
s=sum([j*k for j,k in c.items()])
for x in b:
    s=s-x[0]*c[x[0]]+x[1]*c[x[0]]
    c[x[0]],c[x[1]]=0,c[x[0]]+c[x[1]]
    print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
Q = int(input())
bc = [[int(i) for i in input().split()] for j in range(Q)]
 
counter = [0] * 1000000
for i in a:
    counter[i] += 1

ans = sum(a)
 
for _ in bc:
    ans = ans + counter[_[0]] * _[1] - counter[_[0]] * _[0]
    counter[_[1]] += counter[_[0]]
    counter[_[0]] = 0
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
q = int(input())

d = {}
for x in arr:
    d[x] = d.get(x,0) + 1

tot = sum(arr)

for _ in range(q):
    b,c = [int(x) for x in input().split()]

    if b not in d:
        print(tot)
    else:
        diff = (c-b)*d[b]
        tot+=diff
        print(tot)
        val = d[b]
        del d[b]
        d[c] = d.get(c,0) + val

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
q = int(input())
a_dict = dict()
for i in a:
    if i in a_dict:
        a_dict[i] = a_dict[i] + 1
    else:
        a_dict[i] = 1
a_sum = sum(a)

for i in range(q):
    b,c = map(int,input().split())
    if not b in a_dict:
        print(a_sum)
        continue
    a_sum = a_sum - a_dict[b]*b + a_dict[b]*c
    if c in a_dict:
        a_dict[c] = a_dict[c] + a_dict[b]
    else:
        a_dict[c] = a_dict[b]
    a_dict[b] = 0
    print(a_sum)

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数を数えておく
    cnt[val]+=1
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
    b,c=map(int,input().split())
    diff=(c-b)*(cnt[b]) #各クエリにおいて数列Aの総和は(値がBiである要素の個数)*(Ci-Bi)だけ変化する
    sums+=diff
    print(sums) 
    cnt[c]+=cnt[b] #値がCi,Biである要素の個数を更新する
    cnt[b]=0

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = tuple(map(int, input().split()))
dic = defaultdict(int)

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

base = sum(A)

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

Submission status: Accepted

Solution code:
import numpy as np


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

sumA = sum(A)
cnt_num = np.zeros(10**5 + 1)

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

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

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

s = list(map(int, input().split()))
n=s[0]
a = np.array(list(map(int, input().split())))
s = list(map(int, input().split()))
q=s[0]
num=defaultdict(int)
ans=0

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = list()
C = list()
for i in range(Q):
  b, c = map(int, input().split())
  B.append(b)
  C.append(c)

A_sum = sum(A)
num_count = [0] * (10 ** 5)

for a in A:
  num_count[a-1] += 1
for i in range(Q):
  if num_count[B[i]-1] != 0:
    A_sum += (C[i] - B[i]) * num_count[B[i]-1]
    print(A_sum)
    num_count[C[i]-1] += num_count[B[i]-1]
    num_count[B[i]-1] = 0
  else:
    print(A_sum)

Submission status: Accepted

Solution code:
ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=nl()
nums = [0]*10**6
for i in range(n):
  nums[a[i]]+=1
q=ni()
ans=0
for i in range(len(nums)):
  ans+=nums[i]*i

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

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

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

    S = sum(A)
    cnt = defaultdict(int)
    for a in A:
        cnt[a] += 1
    for _ in range(int(input())):
        b, c = map(int, input().split())
        nb = cnt[b]
        cnt[c] += nb
        cnt[b] = 0
        S += (c - b) * nb
        print(S)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#関数リスト
import sys
from collections import defaultdict
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

n = I()
mylist = LI()
q = I()
d = defaultdict(int)

for i in mylist:
    d[i] += 1
result = sum(mylist)

for i in range(q):
    pastN, nextN= MI()
    num = d[pastN]
    result += num * (nextN-pastN)
    print(result)
    d[pastN] = 0
    d[nextN] += num

Submission status: Accepted

Solution code:
import collections
N = int(input())
a = [int(x) for x in input().split()]
aa = collections.Counter(a)
A = list(aa.items())
Alisted = [0]*(10**5+1)
for i in range(len(A)):
  Alisted[A[i][0]] = A[i][1]
Q = int(input())
BC = [[int(x) for x in input().split()]for i in range(Q)]

Sum = sum(a)
for i in range(Q):
  b = BC[i][0]
  c = BC[i][1]
  num = Alisted[b]
  Sum += (c-b)*num
  print(Sum)
  Alisted[b]=0
  Alisted[c]+=num

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
from collections import defaultdict
s = defaultdict(int)
f = {}
ans = 0
for i in a:
  s[i] += 1
  f[i] = None
  ans += i

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
TMP=sum(A)
Q=int(input())
import collections
List=collections.Counter(A)
for i in range(Q):
  S,T=map(int,input().split())  
  TMP=TMP+(T-S)*List[S]
  print(TMP)  
  List[T]+=List[S]
  List[S]=0

Submission status: Accepted

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

array = dict()
for i in data:
  if i in array:
    array[i] += 1
  else:
    array[i] = 1
    
total = 0
for i, j in array.items():
  total += i*j
  
for i in range(Q):
  dt = 0
  quary = [int(i) for i in input().split()]
  if quary[0] not in array:
    pass
  elif quary[1] in array:
    dt = (quary[1]-quary[0])*array[quary[0]]
    array[quary[1]] += array[quary[0]]
    del array[quary[0]]
  else:
    dt = (quary[1]-quary[0])*array[quary[0]]
    array[quary[1]] = array[quary[0]]
    del array[quary[0]]
  
  total += dt
  print(total)

Submission status: Accepted

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

total = sum(nums)

lst = [0] * 100001

for num in nums:
  lst[num] += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
q=int(input())
numl=collections.Counter(a)
s=sum(a)
for qq in range(q):
  x,y=map(int,input().split())
  s+=numl[x]*(y-x)
  print(s)
  numl[y]+=numl[x]
  numl[x]=0

Submission status: Accepted

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

d=dict()
sum=0
for i in A:
  if not i in d:
    d[i]=0
  d[i]+=1
  sum+=i
#counterと同じ
for i in range(int(input())):
  b,c=map(int,input().split())
  if not c in d:
    d[c]=0
  if not b in d:
    d[b]=0
    
  sum=sum-(d[b]*b)
  sum=sum-(d[c]*c)
  d[c]+=d[b]
  d[b]=0
  sum=sum+(d[c]*c)
  #print(d)
  print(sum)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
d = dict() 
for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1
s = sum(a)
for _ in range(int(input())):
  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]
    d[b] = 0
  print(s)

Submission status: Accepted

Solution code:
import sys



def solve(vals, queries):
    nv = len(vals)
    nq = len(queries)
    # get freqs
    freqs = {}
    tot0 = 0
    for v in vals:
        if not v in freqs:
            freqs[v] = 1
        else:
            freqs[v] += 1
        tot0 += v

    for b,c in queries:
        if b in freqs:
            tot0 += freqs[b]*(c-b)
            if not c in freqs:
                freqs[c] = 0
            freqs[c] += freqs[b]
            del freqs[b]
        print(tot0)
        

        


if __name__ == '__main__':
    IN = [x.strip() for x in sys.stdin.readlines()]

    N = int(IN[0])
    vals = [int(x) for x in IN[1].split(' ')]
    Q = int(IN[2])
    queries = []
    for i in range(Q):
        b,c = [int(x) for x in IN[3+i].split(' ')]
        queries.append((b,c))
    solve(vals, queries)

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

def main():
    n = int(input())
    a = list(map(int,input().split()))
    q = int(input())
    cnt = [0]*(10**5+7)
    for i in range(n):
        cnt[a[i]]+=1
    p = sum(a)
    for i in range(q):
        b,c = map(int,input().split())
        d = cnt[b]
        e = cnt[c]
        diff = d*(c-b)
        p += diff
        cnt[c]+=d
        cnt[b]-=d
        print(p)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dd = defaultdict(int)
s = 0
for i in a:
    s += i
    dd[i] = dd[i] + 1

q = int(input())
for i in range(q):
    bi, ci = map(int, input().split())
    if bi in dd:
        dd[ci] = dd[ci] + dd[bi]
        s = s - bi * dd[bi] + ci * dd[bi]
    dd[bi] = 0
    print(s)

Submission status: Accepted

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

d = {}
sum = sum(a)

for i in a:
  if i in d:
    d[i] += 1
  else:
    d[i] = 1

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

Submission status: Accepted

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

s = sum(a)

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

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

    print(s)

Submission status: Accepted

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

sum_ = sum(A)
element_count_dict = {}
for elm in A:
    element_count_dict[elm] = element_count_dict.get(elm, 0) + 1
for _ in range(Q):
    B, C = list(map(int, input().split()))
    if B in element_count_dict:
        count_B = element_count_dict[B]
        element_count_dict[C] = element_count_dict.get(C, 0) + count_B
        sum_ = sum_ - B * count_B + C * count_B
        element_count_dict[B] = 0
    print(sum_)

Submission status: Accepted

Solution code:
#N, K = map(int, input().split())
#p = list(map(int, input().split()))
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
A_count_list = collections.Counter(A)
A_sum = sum(A)
B = [0] * Q
C = [0] * Q
for _ in range(Q):
    B, C = map(int, input().split())
    A_sum += (C - B)*A_count_list[B]
    A_count_list[C] += A_count_list[B]
    A_count_list[B] = 0
    print(A_sum)

Submission status: Accepted

Solution code:
import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    max_num = 10**5
    n = int(input())
    a_list = list(map(int, input().split()))
    q = int(input())
    
    query = [map(int, input().split()) for _ in range(q)]
    num = [0 for _ in range(max_num+1)]
    for i in a_list:
        num[i] += 1

    ans = sum(a_list)

    for b,c in query:
        n = num[b]
        num[b] = 0
        num[c] += n
        ans += (c-b)*n
        print(ans)

    
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
for i in range(Q):
    B[i], C[i] = map(int, input().split())

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

for i in range(Q):
    total -= B[i] * cnt[B[i]]
    total += C[i] * cnt[B[i]]
    cnt[C[i]] += cnt[B[i]]
    cnt[B[i]] = 0
    print(total)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A_list = list(map(int, input().split()))
A_count_list = collections.Counter(A_list)
A_sum = sum(A_list)
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    A_sum += (C - B)*A_count_list[B]
    A_count_list[C] += A_count_list[B]
    A_count_list[B] = 0
    print(A_sum)

Submission status: Accepted

Solution code:
import numpy as np
from numba import njit

n = int(input())
A = list(map(int,input().split()))
q = int(input())
BC = [list(map(int,input().split())) for _ in range(q)]
A = np.array(A)

ans = sum(A)

#aの個数を管理するlist a_num
a_num = [0]*10**5
for  a in A:
    a_num[a-1]+=1

for bc in BC:
    change = bc[1]-bc[0]
    ans += change*a_num[bc[0]-1]
    a_num[bc[1]-1] += a_num[bc[0]-1]
    a_num[bc[0]-1] = 0
    print(ans)

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
from math import gcd
from collections import Counter as cc

def main():
    n=int(input())
    l=list(map(int,input().split()))
    sm=sum(l)
    cnt=cc(l)
    q=int(input())
    for _ in range(q):
        p,r=map(int,input().split())
        sm-=(p*cnt[p])
        cnt[r]+=cnt[p]
        sm+=(r*cnt[p])
        cnt[p]=0
        print(sm)



    


# region fastio

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

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
import math
import collections
from collections import deque 
from functools import reduce

# input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
c = collections.Counter(a)
c_n = np.array([(k, v) for k, v in c.items()])
total = np.dot(c_n.T[0], c_n.T[1])
q = int(input())
for _ in range(q):
    cf, ca = map(int, input().split())
    num = c[cf]
    if ca in c:
        c[ca] += c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    else:
#         sd[ca] = sd[cf]
        c[ca] = c[cf]
        c[cf] = 0
#         del sd[cf]
#         del c[cf]
    total += num * (ca - cf)
    print(total)

Submission status: Accepted

Solution code:
import collections

def main():
    n = int(input())
    a = list(map(int, input().split()))
    
    cnt = collections.defaultdict(int)
    for var in a:
        cnt[var] += 1
    
    sum_a = sum(a)
    
    q = int(input())
    for _ in range(q):
        b, c = list(map(int, input().split()))
        diff = (c-b) * cnt[b]
        sum_a += diff
        print(sum_a)
        cnt[c] += cnt[b]
        cnt[b] = 0
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin

n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
d = {}
s = 0
for i in a:
    s += i
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1
for _ in range(int(stdin.readline())):
    b, c = list(map(int, stdin.readline().split()))
    if b in d:
        s += d[b]*(c-b)
        if c not in d:
            d[c] = d[b]
        else:
            d[c] += d[b]
    d[b] = 0
    print(s)

Submission status: Accepted

Solution code:
dic={}
n=int(input())
su=0
for i in input().split():
    i=int(i)
    if i in dic.keys():
        dic[i]+=1
    else:
        dic[i]=1
    su+=i
q=int(input())
for cas in range(q):
    b,c=map(int,input().split())
    if b in dic.keys():
        su+=(c-b)*dic[b]
        if c in dic.keys():
            dic[c]+=dic[b]
        else:
            dic[c]=dic[b]
        dic[b]=0
    print(su)

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

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

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

for b, c in zip(m, m):
    bcnt=lst[b]
    ans+=(c-b)*bcnt
    lst[c]+=bcnt
    lst[b]=0
    print(ans)

Submission status: Accepted

Solution code:
N = int(input())
l = [0]*(10**5+1)
A = list(map(int,input().split()))
Q = int(input())
for a in A:
  l[a] += a
suml = sum(l)
for _ in range(Q):
  b,c = map(int,input().split())
  suml += (l[b]//b*c - l[b])
  l[c] += l[b]//b*c
  l[b] = 0
  print(suml)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

num = collections.Counter(A)

S = sum(A)
slist = []

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

[print(i) for i in slist]

Submission status: Accepted

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