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,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1
 
        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][max(0,r-(1<<N))]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][max(0,r-(1<<N))]):
            b=a
        return b
    
    # return boundary index of r such that func({table[i]} =< x , i in [pos,r]
    def right_bound(self,pos,x):
        k=(self.size-pos).bit_length()
        for j in range(k)[::-1]:
            nx=pos+(1<<j)
            if nx<n and self.query(pos,nx+1)<=x:
                pos+=(1<<j)
        return pos
    
    # return boundary index of l such that func({table[i]} =< x , i in [l,pos]
    def left_bound(self,pos,x):
        k=pos.bit_length()
        for j in range(k)[::-1]:
            nx=pos-(1<<j)
            if 0<=nx and self.query(nx,pos+1)<=x:
                pos-=(1<<j)
        return pos
 
    def __str__(self):
        return str(self.table[0])
 
    def print(self):
        for i in self.table:
            print(*i)


show_flg=False
show_flg=True


ans=0

n=I()
a=LI()
d=defaultdict(int)

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

q=I()
for i in rep(q):
    b,c=LI()
    ans+=(c-b)*d[b]
    d[c]+=d[b]
    d[b]=0
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


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

    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    d = [0 for _ in range(10 ** 5)]
    ans = sum(a)

    for ai in a:
        d[ai - 1] += 1

    for i in range(q):
        bi, ci = map(int, input().split())

        bi_count = d[bi - 1]
        ans += (ci - bi) * bi_count
        print(ans)

        d[ci - 1] += d[bi - 1]
        d[bi - 1] = 0


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())
sA = sum(A)
cA = Counter(A)
for i in range(q):
    b,c = map(int, input().split())
    diff = 0
    if cA.get(b):
        diff = (c-b) *cA[b]
    sA += diff
    print(sA)
    cA[c] += cA[b]
    cA[b] = 0

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    x = int(input())
    bc = [list(map(int, input().split())) for _ in [0]*x]
    ans = [0]*100001
    for i in a:
        ans[i] += 1
    ans2 = sum(a)
    for b, c in bc:
        ans2 += (c-b)*ans[b]
        ans[c] += ans[b]
        ans[b] = 0
        print(ans2)


main()

Submission status: Accepted

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

Submission status: Accepted

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

S = sum(A)

D = dict()
for a in A:
    if a in D:
        D[a] += 1
    else:
        D[a] = 1

Q = int(input())

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
d = dict()
for a in A:
    v = d.get(a, 0)
    d[a] = v+1
S = sum(A)
Q = int(input())
B = []
C = []
for q in range(Q):
    b, c = map(int,input().split())
    v = d.get(b, 0)
    S += v*(c-b)
    d[b] = 0
    d[c] = d.get(c,0) + v
    print (S)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys
import math
import time
#import numpy as np
import collections
from collections import deque
from collections import Counter
import queue
import copy
import bisect
import heapq
import itertools


#sys.setrecursionlimit(10**7)
#N, Q = map(int, input().split())
#G = [list(input()) for i in range(H)]
#INF = V * 10001
#A = [int(i) for i in input().split()]
#AB = [list(map(int, input().split())) for _ in range(K)]

N = int(input())
A = [int(i) for i in input().split()]
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
Num = [0]*(10**5)
ans = 0

for i in range(len(A)):
  #print(A[i])
  Num[A[i]-1] += 1
  ans += A[i]

for i in range(Q):
  ans -= BC[i][0]*Num[BC[i][0]-1]
  temp = Num[BC[i][0]-1]
  Num[BC[i][0]-1] = 0
  ans += temp*BC[i][1]
  Num[BC[i][1]-1] += temp
  print(ans)

Submission status: Accepted

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

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

ans = sum(A)

Q = int(input())

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

    ans -= B * cnt[B]
    ans += C * cnt[B]

    cnt[C] += cnt[B]
    cnt[B] = 0

    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def solve():
    N = int(input())
    A = list(map(int,input().split()))
    counter = Counter(A)
    ans = []

    sm = sum(A)
    Q = int(input())
    for i in range(Q):
        b, c = map(int,input().split())
        sm -= counter[b] * b
        sm += counter[b] * c
        counter[c] += counter[b]
        counter[b] = 0
        ans.append(sm)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict

N, _A, Q, *val = [[*map(int, line.split())] for line in open(0)]
N = N[0]
Q = Q[0]

A = defaultdict(int)
for _a in _A:
    A[_a] += 1

ans = sum(_A)
for v in val:
    if v[0] in A.keys():
        num = A[v[0]]
        A[v[0]] = 0
        A[v[1]] += num
        ans += (v[1] - v[0]) * num
    print(ans)

Submission status: Accepted

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

cnt = {}
for i in a:
  if not i in cnt:
    cnt[i] = 0
  cnt[i] += 1
  
queries = []
for i in range(q):
  b, c = map(int, input().split())
  queries.append((b, c))

ans = sum(a)  
  
for (b, c) in queries:
  if b in cnt:
    ans -= cnt[b]*b
    ans += cnt[b]*c
    if not c in cnt:
      cnt[c] = 0
    cnt[c] += cnt[b]
    cnt[b] = 0
  print(ans)

Submission status: Accepted

Solution code:
import collections

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

T=sum(A)
D=collections.Counter(A)

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

Submission status: Accepted

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

q = int(input())

cnt = [0] * 100001

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

while q:
	b, c = map(int, input().split())
	sum += (c - b) * cnt[b]
	cnt[c] += cnt[b]
	cnt[b] = 0
	q -= 1
	print(sum)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
Q=int(input())
count=[0]*(10**5+1)
for a in A:
    count[a]+=1

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

Submission status: Accepted

Solution code:
import sys
import math
#sys.stdin=open('input.txt','r')
#sys.stdout=open('output.txt','w')
from sys import stdin,stdout
from collections import deque,defaultdict
from math import ceil,floor,inf,sqrt,factorial,gcd,log2
from copy import deepcopy
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
mod=1000000007
n=ii1()
arr=iia()
dp=[0]*100005
for i in range(n):
    dp[arr[i]]+=1
q=ii1()
s=sum(arr)
for i in range(q):
    b,c=iia()
    s+=(dp[b]*(c-b))
    dp[c]+=dp[b]
    dp[b]=0
    print(s)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(i) for i in input().split()]
Q = int(input())
B, C = [], []
for i in range(Q):
	b, c = map(int, input().split())
	B.append(b)
	C.append(c)
	
dic = Counter(A)
ans = 0
for k, v in dic.items():
	ans += k*v
for i in range(Q):
	b, c = B[i], C[i]
	dic[c] += dic[b]
	ans += - b*dic[b] + c*dic[b]
	del dic[b]
	print(ans)

Submission status: Accepted

Solution code:
import math

input_num = int(input())
input_numline = list(map(int,input().split(' ')))
q = int(input())

op_list = []
for i in range(q):
    op_list.append(list(map(int,input().split(' '))))

maxnum = 100000

num_list = [0 for m in range(maxnum+1)]

for n in input_numline:
    num_list[n] += 1

ans = 0

for j in range(maxnum+1):
    ans += j*num_list[j]

for o in op_list:
    ans -= o[0]*num_list[o[0]]
    ans += o[1]*num_list[o[0]]
    num_list[o[1]] += num_list[o[0]]
    num_list[o[0]] = 0

    print(ans)

Submission status: Accepted

Solution code:
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)
 
S = sum(A)
memory = [0] * 100001
for num in A:
    memory[num] += 1
for i in range(Q):
  S = S + memory[B[i]] * (C[i]- B[i])
  print(S)
  memory[C[i]] += memory[B[i]]
  memory[B[i]] = 0

Submission status: Accepted

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

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

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

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

    SUM = SUM - b * numbers[b]
    SUM = SUM + c * numbers[b]
    numbers[c] += numbers[b]
    numbers[b] = 0
    print(SUM)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#D
#バケットnum[v]:=A1,A2,...,Anの中に値vが何個あるか　を作って考える
n = int(input())
a = list(map(int,input().split()))
q = int(input())
#合計を計算しておく
sum_a = sum(a)
#バケットの作成
v = [0 for _ in range(10**5)]
for i in range(n):
    v[a[i]-1] += 1
# main loop    
for i in range(q):
    b,c = map(int,input().split())
    sum_a += (c - b)* v[b-1]
    v[c-1] += v[b-1]
    v[b-1] = 0
    print(sum_a)

Submission status: Accepted

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

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

for i in range(Q):
    S_next = S + (C[i] - B[i]) * memory[B[i]]
    print(S_next)
    S = S_next
    memory[C[i]] += memory[B[i]]
    memory[B[i]] = 0

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
bc = [list(map(int,input().split())) for _ 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 + (bc[i][1]- bc[i][0]) * p[bc[i][0]]

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

    print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	D_fix_2
# CreatedDate:  2020-06-22 17:32:46 +0900
# LastModified: 2020-06-22 17:39:47 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd


def main():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = [0]*100001
    for a_ in a:
        cnt[a_] += 1

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




if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dist = [0]*100000
ans = sum(a)
for i in a:
    dist[i-1] += 1

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
dist = [0]*100000
ans = sum(a)
for i in a:
    dist[i-1] += 1

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

Submission status: Accepted

Solution code:
N = int(input())
a=list(map(int, input().split()))
Q = int(input())
num_a =[0]*100001
num_b = []
sum_a = sum(a)
b=[]
c=[]
for i in a:
  num_a[i]+= 1
for i in range(Q):
  b1,c1=map(int, input().split())
  b.append(b1)
  c.append(c1)
for i in range(Q):
  if num_a[b[i]]==0:
    num_b.append(0)
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  else:
    num_b.append(num_a[b[i]])
    num_a[c[i]] += num_a[b[i]]
    num_a[b[i]] = 0
    sum_a = sum_a - b[i]*num_b[i] +c[i]*num_b[i]
  print(sum_a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
# 辞書型で値をint型にする
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数をカウントアップ
 cnt[val]+=1
# cntの出力結果　入力例2
# defaultdict(<class 'int'>, {1: 4})
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
 b,c=map(int,input().split())
 #差は(Ci-Bi)*(値がBiである要素の個数)
 diff=(c-b)*(cnt[b]) 
 #差分合計値を更新
 sums+=diff
 print(sums) 
 #クエリごとに値bをcに更新してbを消す
 cnt[c]+=cnt[b] 
 cnt[b]=0
#  defaultdict(<class 'int'>, 
# {1: 0, 2: 2, 3: 1, 4: 1})1回目
#  defaultdict(<class 'int'>, 
# {1: 0, 2: 2, 3: 0, 4: 2})2回目

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(a)

s = sum(a)

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import os
import sys
from atexit import register
from io import BytesIO
sys.stdin = BytesIO(os.read(0, os.fstat(0).st_size))
sys.stdout = BytesIO()
register(lambda: os.write(1, sys.stdout.getvalue()))
input = lambda: sys.stdin.readline().rstrip('\r\n')
raw_input = lambda: sys.stdin.readline().rstrip('\r\n')

n = int(input())
seq = [int(x) for x in input().split()]
d = {}
s = 0
for val in seq:
    try:
        d[val] += 1
    except:
        d[val] = 1
    s += val
for _ in range(int(input())):
    b,c = (int(x) for x in input().split())
    if b in d:
        s -= b * d[b]
        s += c * d[b]
        print(s)
        try:
            d[c] += d[b]
        except:
            d[c] = d[b]
        d[b] = 0
    else:
        print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N = INT()
A = LIST()

C = Counter(A)
cur = sum(A)
Q = INT()
for _ in range(Q):
    b, c = MAP()
    cur -= b * C[b]
    cur += c * C[b]
    print(cur)
    C[c] += C[b]
    C[b] = 0

Submission status: Accepted

Solution code:
import collections as c

n = int(input())

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

q = int(input())

s = sum(a)

cnt = c.Counter(a)

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

Submission status: Accepted

Solution code:
N=int(input())

A=[]
A=list(map(int,input().split()))
wa=sum(A)
AA=[0]*(10**5+1)
for i in A:
    AA[i]=AA[i]+1
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
    B[i],C[i]=map(int,input().split())
    #print('{wa},{C},{B},{AA}'.format(wa=wa,C=C[i],B=B[i],AA=AA[B[i]]))
    #print('{wa},{C},{B},{AA}'.format(wa=wa, C=C[i], B=B[i], AA=AA[B[i]]))
    wa=wa+(C[i]-B[i])*AA[B[i]]
    AA[C[i]]=AA[C[i]]+AA[B[i]]
    AA[B[i]]=0
    print(wa)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#15:30
n = int(input())
a = list(map(int,input().split()))
b = {}
for x in a:
  b[x] = 0
q = int(input())
inp = []
for _ in range(q):
  x,y = map(int,input().split())
  b[x] = 0
  b[y] = 0
  inp.append([x,y])
for x in a:
  b[x] += 1
ans = sum(a)
for z in inp:
  x,y = z
  ans += (y-x) * b[x]
  b[x],b[y] = 0,b[x]+b[y]
  print(ans)

Submission status: Accepted

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

for _ in range(q):
    b, q = map(int, input().split())
    if b in count:
        sm -= count[b] * b
        sm += count[b] * q
        print(sm)
    else:
        print(sm)
    if q in count:
        count[q] += count[b]

        count[b] = 0
    else:
        count[q] = count[b]

        count[b] = 0

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
a = list(map(int, input().split()))
dic = {}
for aa in a:
    if aa in dic:
        dic[aa] += 1
    else:
        dic[aa] = 1
a_sum = sum(a)
q = int(input())

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

Submission status: Accepted

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

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

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

for i in range(q):
    b,c=map(int,input().split())
    if count[b]!=0:
        sum+=(c-b)*count[b]
        count[c]+=count[b]
        count[b]=0
    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)
for i in range(q):
    b, c = map(int, input().split())
    ans += (c-b)*A[b]
    print(ans)
    A[c] += A[b]; A[b] = 0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
dic = Counter(a)
su = sum(a)
q = inp()
for _ in range(q):
    b,c = inpl()
    su += dic[b] * (c-b)
    print(su)
    dic[c] += dic[b]
    dic[b] = 0

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [0]*(10**5+1)
all_sum = sum(a)
for i in a:
    l[i] += 1
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    cnt = l[b]
    l[c] += cnt 
    all_sum += cnt * (c-b)
    l[b] = 0
    print(all_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)
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:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
count = Counter(A) #not dict!!
temp_sum = sum(A)
for _ in range(Q):
    before, after = map(int, input().split())
    temp_sum += (after - before) * count[before]
    count[after] += count[before]
    count[before] = 0
    print(temp_sum)