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
import collections

N = int(input())
A = list(map(int, sys.stdin.readline().split()))
Q = int(input())
BC = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

A_dic = collections.Counter(A) 
S = sum(A)
for i in range(Q):
    num = A_dic[BC[i][0]]
    A_dic[BC[i][0]] = 0
    A_dic[BC[i][1]] += num
    S += (BC[i][1] - BC[i][0]) * num
    print(S)

Submission status: Accepted

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

q = int(input())

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

Submission status: Accepted

Solution code:
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 _ in range(q):
        b, c = map(int, input().split())
        s[c] += s[b]
        sa += (c-b)*s[b]
        s[b] = 0
        print(sa)

main()

Submission status: Accepted

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

answer = sum(a)
a_num_cnt = {}

for i in range(n):
    num = a[i]

    if num in a_num_cnt:
        a_num_cnt[num] += 1
    else:
        a_num_cnt[num] = 1

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

    if b in a_num_cnt:
        cnt = a_num_cnt[b]
        answer += (increament * cnt)
        a_num_cnt[b] -= cnt

        if c in a_num_cnt:
            a_num_cnt[c] += cnt
        else:
            a_num_cnt[c] = cnt


    print(answer)

Submission status: Accepted

Solution code:
n = int(input())
r = list(map(int,input().split(" ")))
ar = {i: 0 for i in range(1,10 ** 5 + 1)}
s = sum(r)
for a in r:
    ar[a] += 1
q = int(input())
for i in range(q):
    x,y = map(int,input().split(" "))
    s += (y - x) * ar[x]
    ar[y] += ar[x]
    ar[x] = 0
    print(s)

Submission status: Accepted

Solution code:
N=int(input())
array=map(int,input().split())
A=[]
for i in array:
    A.append(i)

dict_num={i:0 for i in range(100050)}
Q=int(input())
matrix=[]
for i in range(Q):
    matrix.append(list(map(int,input().split())))

#全数値の合計計算
sum=0
#各数字の出現回数の計測
for i in range(N):
    dict_num[A[i]]+=1
    sum+=A[i]

#合計の再計算 & 数字の出現回数の再計算
for i in matrix:
    sum+=(i[1]-i[0])*dict_num[i[0]]
    dict_num[i[1]]+=dict_num[i[0]]
    dict_num[i[0]]=0
    print(sum)

Submission status: Accepted

Solution code:
# coding:utf-8
import collections

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


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

    print(sum_a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
from sys import stdin
data = stdin.readlines()

n = int(data[0].split()[0])
a = [int(s) for s in data[1].split()]
q = int(data[2].split()[0])

sum = sum(a)

l = []
for i in range(q):
    l.append(int(data[i+3].split()[0]))
    l.append(int(data[i+3].split()[1]))

d = collections.Counter(a)

for i in range(q):
    sum += (l[2*i+1]-l[2*i]) * d[l[2*i]]
    d[l[2*i+1]] += d[l[2*i]]
    d[l[2*i]] = 0
    print(sum)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
AC = Counter(A)
S = sum(A)
Q = int(input())
for _ in range(Q):
  B,C = map(int, input().split())
  if B not in AC:
    pass
  else:
    count = AC[B]
    AC[B] = 0
    S = S + (C-B)*count
    if C in AC:
      AC[C] += count
    else:
      AC[C] = count
  print(S)

Submission status: Accepted

Solution code:
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8') 
inf = float('inf') ;mod = 10**9+7 
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n = int(input())
A = list(map(int, input().split()))
ans = sum(A)
cnt = collections.Counter(A)
#print(cnt)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    ans += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    #print(cnt)
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
x=dict()
for i in range(N):
    val=A[i]
    if val in x:
        x[val]+=1
    else:
        x[val]=1

S=sum(A)
#print(S)
for i in range(Q):
    b,c=map(int,input().split())
    if b in x:
        pass
    else:
        x[b]=0
    p=c*x[b]
    d=b*x[b]
    if c in x:
        pass
    else:
        x[c]=0
    x[c]+=x[b]
    x[b]=0
    S=S+p-d
    print(S)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())

A = [int(x) for x in input().split()]
T = sum(A)
Z = Counter(A)

Q = int(input())

for _ in range(Q):
  B,C = map(int,input().split())
  x = Z[B]
  y = Z[C]
  Z.pop(B,0)
  Z[C] = x+y
  T = T-(B*x)+(C*x)
  print(T)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

Solution code:
mod = int(1e9+7)
def add(a, b):
    c = a + b
    if c >= mod:
        c -= mod
    return c

def main():
    #A, B = [int(x) for x in raw_input().split()]
    n = int(raw_input())
    
    arr = [int(x) for x in raw_input().split()]
    
    cnt = {}
    
    cur_sum = 0
    
    for num in arr:
        cnt[num] = cnt.get(num, 0) + 1
        cur_sum += num 
    
    q = int(raw_input())
    
    for _ in range(q):
        frm, to = [int(x) for x in raw_input().split()]
        
        frm_cnt, to_cnt = cnt.get(frm, 0), cnt.get(to, 0)
        
        diff = to - frm
        
        total_diff = frm_cnt * diff
        
        cur_sum += total_diff
        
        cnt[to] = to_cnt + frm_cnt
        
        cnt[frm] = 0
        
        print(cur_sum)
        
        
           
        
    
    #queries = [ for x in raw_input().split()]
    

main()

Submission status: Accepted

Solution code:
n = int(input())
A = map(int, input().split())
q = int(input())
BC = [None for i in range(q)]
for i in range(q):
    b,c = map(int, input().split())
    BC[i] = (b,c)

count = [0 for i in range(10**5+2)]
for a in A:
    count[a]+=1

ans = 0
for i in range(10**5+2):
    ans+=(i*count[i])

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ans=0
anum={}
for i in range(n):
    ans+=a[i]
    if a[i] in anum:
        anum[a[i]]+=1
    else:
        anum[a[i]]=1
q=int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

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

first_sum = sum(t)

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

for i in range(n):
    memo[t[i]] += 1

q=int(input())

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

for aa in a:#initialize
  d[aa]+=1

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

Submission status: Accepted

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

# D - Replacing
def get_sum(dic):
	sum = 0
	
	for k, v in dic.items():
		sum += k * v
	
	return sum


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

for ai in a:
	dic.setdefault(ai, 0)
	dic[ai] += 1

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

	count = dic.pop(b, 0)
	
	if count > 0:
		dic.setdefault(c, 0)
		dic[c] += count

	if i == 0:	
		sum = get_sum(dic)
	else:
		sum += (c - b) * count
	
	print(sum)

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

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

for b,c in bc:
    if b not in cnt:
        cnt[b] = 0
    if c not in cnt:
        cnt[c] = 0
    allsum += (c-b)*cnt[b]
    cnt[c] += cnt[b]
    cnt[b] =0
    print(allsum)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
import collections

def set_debug(debug_mode=False):
    if debug_mode:
        fin = open('input.txt', 'r')
        sys.stdin = fin


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


def get(s):
    return str(s % 9) + '9' * (s // 9)

if __name__ == '__main__':
    # set_debug(True)

    # t = int(input())
    t = 1

    for ti in range(1, t + 1):
        n = int(input())
        A = int_input()

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

        res = 0

        for x in A:
            res += x
            d[x] += 1

        q = int(input())

        for _ in range(q):
            b, c = int_input()

            res += (c - b) * d[b]
            d[c] += d[b]
            d[b] = 0

            print(res)

Submission status: Accepted

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

    g = {}
    ans = 0
    for a in A:
        ans += a
        if a not in g:
            g[a] = 1
        else:
            g[a] += 1

    for i in range(Q):
        B, C = tuple(BC[i])
        if B in g:
            t = g.pop(B)
            ans += t * (C - B)
            if C in g:
                g[C] += t
            else:
                g[C] = t
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())
numbers = list(map(int,input().split()))
numOfOperation = int(input())
dic = {}

for num in numbers:
    if num in dic : dic[num] += 1
    else: dic[num] = 1
    

sums = sum(numbers)
for i in range(numOfOperation):
    B,C = map(int,input().split())
    if (B in dic) : 
        cnt = dic[B]
        dic[B] = 0
        if (C not in dic) : dic[C] = cnt
        else : dic[C] += cnt
        sums += cnt * (C - B)
    print(sums)

Submission status: Accepted

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

og_sum = sum(A)

m = {}

for num in A:
    if num not in m:
        m[num] = 1
    else:
        m[num] += 1

for _ in range(Q):
    B, C = map(int, input().split())
    if B in m:
        cnt = m[B]
        new_sum = og_sum - cnt * B + cnt * C

        print(new_sum)
        og_sum = new_sum

        if C in m:
            m[C] += cnt
        else:
            m[C] = cnt

        del m[B]
    else:
        print(og_sum)

Submission status: Accepted

Solution code:
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
gcd = math.gcd
n = ni()
A = list(ma())
q = ni()
co = collections.Counter(A)
s = sum(A)
for i in range(q):
    b,c = ma()
    s = s - co[b]*b +co[b]*c
    co[c] +=co[b]
    co[b] = 0
    print(s)

Submission status: Accepted

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

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

ans  = 0
for i in range(len(A)):
  ans += i * A[i]  

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
a_list = list(map(int,input().split()))
index = defaultdict(int)
total = 0
for a in a_list:
  total += a
  index[a] += 1

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

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    Q = int(input())
    BC = [[int(x) for x in input().split()] for _ in range(Q)]

    ans = sum(A)
    cnt = collections.Counter(A)

    for i in range(Q):
        b, c = BC[i]
        ans -= cnt[b] * b
        ans += c * cnt[b]
        cnt[c] += cnt[b]
        cnt[b] = 0
        print(ans)



    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
###==================================================
### import
#import bisect
#from collections import Counter, deque, defaultdict
#from copy import deepcopy
#from functools import reduce, lru_cache
#from heapq import heappush, heappop
#import itertools
#import math
import sys
### stdin
def input(): return sys.stdin.readline()
def iIn(): return int(input())
def iInM(): return map(int, input().split())
def iInM1(): return map(int1, input().split())
def iInLH(): return list(map(int, input().split()))
def iInLH1(): return list(map(int1, input().split()))
def iInLV(n): return [iIn() for _ in range(n)]
def iInLV1(n): return [iIn()-1 for _ in range(n)]
def iInLD(n): return [iInLH() for _ in range(n)]
def iInLD1(n): return [iInLH1() for _ in range(n)]
def sInLH(): return list(input().split())
def sInLV(n): return [input().rstrip('\n') for _ in range(n)]
def sInLD(n): return [sInLH() for _ in range(n)]
### stdout
OutV = lambda x: print(*x, sep='\n')
### setting
sys.setrecursionlimit(10 ** 6)
### utils
int1 = lambda x: int(x) - 1
### constants
INF = int(1e9)
MOD = 1000000007
dx = (-1, 0, 1, 0)
dy = (0, -1, 0, 1)
###---------------------------------------------------

N = iIn()
A = iInLH()
Q = iIn()
BC = iInLD(Q)

ssum = sum(A)
lst = [0]*100000
for i in range(N):
    lst[A[i]-1] += 1

for i in range(Q):
    n_b = lst[BC[i][0]-1]
    ssum = ssum - BC[i][0] * n_b + BC[i][1] * n_b
    print(ssum)
    lst[BC[i][0]-1] = 0
    lst[BC[i][1]-1] += n_b

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
SUMA = sum(A)
C = collections.Counter(A)
Q = int(input())
BC = [list(map(int,input().split())) for _ in range(Q)]
for bc in BC:
    SUMA += C[bc[0]]*bc[1]-C[bc[0]]*bc[0]
    print(SUMA)
    C[bc[1]] = C[bc[1]]+C[bc[0]]
    C[bc[0]] = 0

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
A.sort()
Q = int(stdin.readline())
D = dict()
S = set(A)
sum=0
count=0

for y in range(0,N):
    sum+=A[y]
    if y>0 and A[y]!=A[y-1]:
        D[A[y-1]]=count
        count=1
    elif y==0:
        count=1
    else:
        count+=1
    if y==N-1:
        D[A[y]]=count

for u in range(0,Q):
    U= list(map(int,stdin.readline().split()))
    if U[0] in D:
        sum+=(D[U[0]])*(U[1]-U[0])
        if U[1] in D:
            D[U[1]]+=D[U[0]]
        else:
            D[U[1]]=D[U[0]]
        D[U[0]]=0


    print(sum)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
col = collections.Counter(a)

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

  col[c]+=col[b]
  col[b]=0

Submission status: Accepted

Solution code:
MX = 100005
n = int(input())
cnt = [0] * MX
a = list(map(int, input().split()))

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

total = 0

for i in range(MX):
    total += i*cnt[i]

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
#import numpy as np
import bisect
import sys
#import sympy
sys.setrecursionlimit(10**6)


def bfs(s,n,node):
    #頂点が探索済みかどうかのチェック配列
    check=[False for _ in range(n)]
    check[s]=True
    #次見る頂点を格納するキュー
    queue=deque([s])
    visited_num=1

    #問題固有の配列
    #color_check=[[True for _ in range(l)] for _ in range(n)]
    color=[-1 for _ in range(n)]
    color[s]=0
    
    while visited_num<n:
        #グラフが全連結ではない場合
        if len(queue)==0:
            #空配列を返す
            #現状までの計算済み配列を返してもいいと思う
            return color

        now_vertex=queue.popleft()
        #インデックスがない場合は
        for next_vertex in node[now_vertex]:


            if check[next_vertex]==True:
                continue

            queue.append(next_vertex)
            check[next_vertex]=True

            #問題固有の計算
            color[next_vertex]=color[now_vertex]+1
            visited_num+=1

    return color

mod=10**9+7
#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))

n=int(input())
tmp=list(map(int,input().split()))
ans=sum(tmp)
tmp=Counter(tmp)
di=defaultdict(int)
for i in tmp.keys():
    di[i]+=tmp[i]

q_num=int(input())

for _ in range(q_num):
    #print(di)
    v,w=map(int,input().split())
    #print(ans)
    ans=ans-di[v]*v+di[v]*w
    di[w]+=di[v]
    del di[v]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
m=list(map(int,input().split()))
d={}
k=0
for i in range(n):
    k+=m[i]
    if m[i] in d:
        d[m[i]]+=1
    else:
        d[m[i]]=1
for x in range(int(input())):
    
    b,c=list(map(int,input().split()))

    
    
    if b in d:
        k+=d[b]*(c-b)
        if c in d:
            d[c]+=d[b]
        else:
            d[c] = d[b]
        del d[b] 
    print(k)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a_l = list(map(int, input().split()))
cnt = collections.Counter(a_l)
q = int(input())

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

Submission status: Accepted

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

a_cnts = {}
a_sum = 0
for an in a:
    if an in a_cnts.keys():
        a_cnts[an] += 1
    else:
        a_cnts[an] = 1
    a_sum += int(an)

q = int(input())

for i in range(q):
    (b, c) = input().split()

    if b in a_cnts.keys():
        hit_cnt = a_cnts[b]
        del a_cnts[b]
        if c in a_cnts.keys():
            a_cnts[c] += hit_cnt
        else:
            a_cnts[c] = hit_cnt
        a_sum += (int(c) - int(b))*hit_cnt

    print(a_sum)

Submission status: Accepted

Solution code:
import sys

def main(n, a_n, q, bc_n):
    m = {}
    for i in range(n):
        if a_n[i] not in m:
            m[a_n[i]] = 0
        m[a_n[i]] += 1

    s = []
    for j in range(q):
        b, c = bc_n[j]

        diff = 0
        if b in m:
            diff = m[b] * c  - m[b] * b
            if c not in m:
                m[c] = m[b]
            else:
                m[c] += m[b]
            del m[b]

        ts = 0
        if len(s) == 0:
            for k, v in m.items():
                ts += k * v
        else:
            ts = s[-1] + diff
        s.append(ts)
    return s


n = int(sys.stdin.readline().strip())
a_n = [int(x) for x in sys.stdin.readline().strip().split(" ")]
q = int(sys.stdin.readline().strip())
bc_n = []
for _ in range(q):
    b, c = [int(x) for x in sys.stdin.readline().strip().split(" ")]
    bc_n.append((b, c))
for i in main(n, a_n, q, bc_n):
    print(i)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# 整数の入力
N = int(input())
A = [int(a) for a in input().split()]
Q = int(input())
process = []
proc_append = process.append
hash = [0]*100001
for i in range(Q):
    proc_append(tuple(input().split()))
    process[i] = tuple(map(int,process[i]))

goukei = sum(A)

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

for b,c in process:
	if hash[b] != 0:
		goukei += (c-b)*hash[b]
		hash[c] += hash[b]
		hash[b] = 0
	print(goukei)

Submission status: Accepted

Solution code:
import collections

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

ans = sum(A)
d = collections.defaultdict(int)

for key in A:
    d[key] += 1

for i in range(Q):
    b,c = BC[i][0],BC[i][1]
    ans += d[b]*(c-b)
    d[c] += d[b]
    d[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
l=[0]*100001
a=sum(A)
for i in A:
    l[i]+=1
for i in range(Q):
    b,c=map(int,input().split())
    a+=(c-b)*l[b]
    l[c]+=l[b]
    l[b]=0
    print(a)

Submission status: Accepted

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

S = sum(A)

idx = dict()
for i in range(len(A)):
	idx.setdefault(A[i], 0)
	idx[A[i]] += 1

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

Submission status: Accepted

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

NumCnt = {}
for a in A:
  if a in NumCnt:
    NumCnt[a]+=1
  else:
    NumCnt[a]=1
    
S = sum(A)
for b,c in zip(B,C):
  if b in NumCnt:
    cnt_c = NumCnt.pop(b)
    S += (c-b)*cnt_c
    if c in NumCnt:
      NumCnt[c] +=cnt_c
    else:
      NumCnt[c] = cnt_c
  else:
    pass
  print(S)

Submission status: Accepted

Solution code:
# Problem D - Replacing

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

# initialization
nums = [0] * (10**5 + 1)
cur_sum = sum(a_nums)
for a in a_nums:
    nums[a] += 1

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

Submission status: Accepted

Solution code:
def kazu_up(kosu, a, kazu):
    if a in kazu:
        kazu[a] += kosu
    else:
        kazu[a] = kosu
    
    return kazu

def kazu_down(a, kazu):
    if a in kazu:
        del kazu[a]
            
    return kazu

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC=[]
kazu = {}

for q in range(Q):
    BC.append(list(map(int, input().split())))
    
A_sum = 0
    
for a in A:
    A_sum += a
    kazu = kazu_up(1, a, kazu)

for bc in BC:
    try:
        A_sum += ( bc[1] - bc[0] ) * kazu[bc[0]]
        print(A_sum)
        kazu = kazu_up(kazu[bc[0]], bc[1], kazu)
        kazu = kazu_down(bc[0], kazu)
        
    except:
        print(A_sum)

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict


def main():
    input = stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    ans = sum(a)
    dic = defaultdict(int)
    for ai in a:
        dic[ai] += 1
    q = int(input())
    bc = [list(map(int, input().split())) for _ in range(q)]
    for b, c in bc:
        count = dic[b]
        ans += count * (c - b)
        print(ans)
        dic[b] -= count
        dic[c] += count


if __name__ == "__main__":
    setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [map(int,input().split()) for _ in range(Q)]
B, C = [i for i in zip(*BC)]
#print(B,C)

dic = {}
for a in A:
  dic[a] = dic.get(a,0) + 1

ans = sum(A)
for q in range(Q):
  bc = C[q] - B[q]
  ans = ans + bc * dic.get(B[q],0)
  dic[C[q]] = dic.get(C[q],0) + dic.get(B[q],0)
  dic[B[q]] = 0
  print(ans)

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    N=I()
    A=LI()
    from collections import defaultdict
    dd = defaultdict(int)
    for i in range(N):
        dd[A[i]]+=1
        
    ans=sum(A)
        
    Q=I()
    for i in range(Q):
        b,c=MI()
        cnt=dd[b]
        ans=ans+cnt*(c-b)
        print(ans)
        dd[c]+=cnt
        dd[b]=0

        
    
    

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)
A=Counter(a)

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

Submission status: Accepted

Solution code:
N = int(input())
A = [0]*N
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]*Q
# for i in range(Q):
#     for j in range(N):
#         if A[j] == B[i]:
#             A[j] = C[i]
#     for k in range(N):
#         S[i] += A[k] 
# for i in range(Q):
#     print(S[i])

cnt = [0] * 100005 # Aの数字の数を格納する，カウント配列
for i in A:
    cnt[i]+=1 

tot = sum(A)
for i in range(Q):
    #合計値の変動
    tot -= B[i]*cnt[B[i]]
    tot -= C[i]*cnt[C[i]]
    #カウント配列の変動
    cnt[C[i]] += cnt[B[i]]
    cnt[B[i]] = 0
    #合計値の変動
    tot += B[i]*cnt[B[i]]
    tot += C[i]*cnt[C[i]]
    print(tot)

Submission status: Accepted

Solution code:
input()
arr = [int(num) for num in input().strip().split(' ')]
q = int(input())

queries = []

for i in range(q):
    query = [ int(num) for num in input().strip().split(' ')]
    queries.append(query)

nums = dict()
summ = 0

for number in arr:
    summ += number
    if number not in nums:
        nums[number] =  1
    else:
        nums[number] += 1

for query in queries:
    curr, new = query
    if curr not in nums: 
        print(summ)
        continue
    count = nums[curr]
    diff = (new-curr)*count
    summ += diff
    del nums[curr]
    if new not in nums:
        nums[new] = count
    else:
        nums[new] += count
    print(summ)

Submission status: Accepted

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from collections import Counter
def resolve():
    n = int(input())
    C = Counter(map(int, input().split()))
    total = 0
    for key, val in C.items():
        total += key * val

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