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 itertools

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

distribution = {}
max_A = max(A)
max_BC = max(list(itertools.chain.from_iterable(BC)))
maximum = max([max_A, max_BC])
# print(max_A, max_BC, maximum)
for i in range(maximum + 1):
    distribution[i] = 0

for Ai in A:
    distribution[Ai] += 1
# print(distribution)

total = sum(A)
for i in range(Q):
    Bi = BC[i][0]
    Ci = BC[i][1]
    num_Bi = distribution.get(Bi)
    diff = (Ci - Bi) * num_Bi

    distribution[Bi] = 0
    # print(num_Bi, distribution.get(Bi), Ci)
    distribution[Ci] += num_Bi

    total += diff
    print(total)

Submission status: Accepted

Solution code:
N =int(input())
A = list(map(int, input().split()))
Q = int(input())
A2 = [0]*(10**5)
B = [0]*Q
C = [0]*Q
for q in range(Q):
    B[q],C[q]=map(int,input().split())
total = 0
Adict = dict()
for n in range(N):
    A2[A[n]-1]+=1
    total+=A[n]
for q in range(Q):
    total = total - B[q]*A2[B[q]-1] + C[q]*A2[B[q]-1]
    A2[C[q]-1] += A2[B[q]-1]
    A2[B[q]-1] = 0
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter

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

x = Counter(A)
s = sum(A)

res = list()
for _ in range(Q):
    b, c = list(map(int, input().split()))
    s += (c - b) * x[b]
    x[c] = x[b] + x[c]
    x[b] = 0
    res.append(s)

for r in res:
    print(r)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())

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

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

for i in range(n):
  z[a[i]]+=1

q=int(input())

y=[]

sam=sum(a)

for i in range(q):
  b,c=map(int,input().split())
  z[c]+=z[b]
  sam-=z[b]*b
  sam+=z[b]*c
  z[b]=0
  #print(z)
  
  y.append(sam)

for i in range(len(y)):
  print(y[i])

Submission status: Accepted

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


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

a = [0]*(10**5+3)

for i in range(N):
    a[A[i]] += 1
    S[0] += A[i]

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

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())
import collections
A=collections.Counter(a)
S=0
for j in range(N):
	S=S+a[j]
for i in range(Q):
	if B[i] in A:
		f=A.pop(B[i])
		if C[i] in A:
			g=A[C[i]]
			h=f+g
		else:
			h=f
		A[C[i]]=h
	else:
		f=0
	S=S+f*(C[i]-B[i])
	print(S)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
mx=max(a)
num=[]
for i in range(100002):
  num.append(0)
bc=[]
for i in range(q):
  b,c=map(int,input().split())
  bc.append([b,c])
sm=0
for i in a:
  num[i]+=1
  sm+=i
for i in bc:
  b=i[0]
  c=i[1]
  sm-=b*num[b]
  sm+=c*num[b]
  num[c]=num[b]+num[c]
  num[b]=0
  print(sm)

Submission status: Accepted

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

  MAX = 10 ** 5

  total = sum(A)
  counts = [0] * (MAX + 1)

  for v in A:
    counts[v] += 1

  for _ in range(Q):
    B, C = list(map(int, input().split()))
    diff = C - B
    t = counts[B]
    counts[B] = 0
    counts[C] += t

    total += diff * t
    print(total)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

total = sum(a)
from collections import Counter
ans = Counter(a)

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
sa=sum(a)
bc=[]
for _ in range(q):
    b,c=map(int,input().split())
    bc.append([b,c])
d={}
for i in range(n):
    if a[i] not in d:
        d[a[i]]=1
    else:
        d[a[i]]+=1

for i in range(q):
    b=bc[i][0]
    c=bc[i][1]
    cb=c-b
    if b in d:
        sa+=cb*d[b]
        if c in d:
            d[c]+=d[b]
            d[b]=0
        else:
            d[c]=d[b]
            d[b]=0

    print(sa)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    N = int(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    A = list(map(int, stdin.readline().rstrip().split()))
    Q = int(stdin.readline().rstrip())
    #BC = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    ans = sum(A)
    counting = Counter(A)
    for i in range(Q):
        B, C = map(int, stdin.readline().rstrip().split())
        dif = C-B
        ans += counting[B]*dif
        counting[C] += counting[B]
        counting[B] = 0
        print(ans)


main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
As = list(map(int,input().split()))
# print(As)
Q = int(input())
Bs = []
Cs = []
for _ in range(Q):
  b,c = map(int,input().split())
  Bs.append(b)
  Cs.append(c)

cnt = Counter(As)
sum0 = sum(As)
for i in range(Q):
  sum0 += cnt[Bs[i]] * (Cs[i] - Bs[i])
  cnt[Cs[i]] += cnt[Bs[i]]
  cnt[Bs[i]] = 0
  print(sum0)

Submission status: Accepted

Solution code:
#4問目
N = int(input())
A = list(map(int, input().split()))
result = sum(A)
dictionaly = {}
for i in A:
    dictionaly[i] = dictionaly.get(i, 0) + 1
RESULT = []
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    sub = C - B
    if B in dictionaly:
        result += (dictionaly[B] * sub)
        dictionaly[C] = dictionaly.get(C,0) + dictionaly[B]
        dictionaly[B] = 0
    RESULT.append(result)
for i in RESULT:
    print(i)

Submission status: Accepted

Solution code:
# D - Replacing

from collections import defaultdict

N = int(input())
A = list(int(a) for a in input().split())
d = defaultdict(int)
ans = 0
for a in A:
    d[a] += 1
    ans += a

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    tmp = d[b]
    d[b] -= tmp
    d[c] += tmp
    ans += -b*tmp + c*tmp
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter as c
n = int(input())
x = list(map(int, input().split()))
d = dict(c(x))
q = int(input())
s = sum(x)
for i in range(q):
    x, y = list(map(int, input().split()))
    if y in d:
        if x in d:
            d[y] += d[x]
        else:
            d[x] = 0
    else:
        if x in d:
            d[y] = d[x]
        else:
            d[x] = 0
    s += d[x]*(y-x)
    print(s)
    d[x] = 0

Submission status: Accepted

Solution code:
import numpy as np

ans = 0

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

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

for a in npA:
	counts[a]+=1

ans = np.sum(npA)

Q=int(input())

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

	if 0 < counts[B]:
		diff = ( C - B ) * counts[B]
		counts[C] += counts[B]
		counts[B] = 0

	ans += diff
	print(ans)

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 = [list(i) for i in zip(*bc)]

app = [0] * 100001
for num in a:
  app[num] += 1

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

Submission status: Accepted

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

numbers = [0] * (10**5+2)
total = sum(A)

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

for _ in range(Q):
    B, C = map(int, input().split())
    tmp = numbers[B]
    #print('tmp: ', tmp)
    diff = (C-B) * tmp
    #print('diff: ', diff)
    total += diff
    numbers[B] = 0
    numbers[C] += tmp
    print(total)
    #print()

Submission status: Accepted

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

n_dic = {}
for i in n_list:
    n_dic.setdefault(i, 0)
    n_dic[i] += 1

result = 0
for k in n_dic:
    result += k * n_dic[k]

for i in range(q):
    b, c = map(int, input().split())
    if b in n_dic:
        n_dic.setdefault(c, 0)
        n_dic[c] += n_dic[b]
        result = result + (c-b)*n_dic[b]
        del n_dic[b]

    print(result)

Submission status: Accepted

Solution code:
import sys
from collections import deque, Counter
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n = I()
    a = list(IL())
    C = Counter(a)
    m = sum(a)
    q = I()
    s = []
    for rep in range(q):
        b,c = IL()
        if b in C:
            m += (c-b)*C[b]
            C[c] += C[b]
            C[b] = 0
        s.append(m)
    for rep in s:
        print(rep)
    return

if __name__=='__main__':
    Main()

Submission status: Accepted

Solution code:
n = int(input())
init = [int(s) for s in input().split()]

a = {}
init_sum = sum(init)

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

q = int(input())

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

    if b not in a:
        a[b] = 0

    ans -= (b * a[b])

    if c not in a:
        a[c] = a[b]
    else:
        a[c] += a[b]

    ans += (c * a[b])

    a[b] = 0

    print(ans)

Submission status: Accepted

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

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

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

bef_ans = 0
for i in range(Q):
    B, C = map(int, input().split())
    tmp = count[B]
    count[B] = 0
    count[C] += tmp
    ans = 0
    if i == 0:
        for j in range(10**5+1):
            ans += j*count[j]
    else:
        ans = bef_ans - B*tmp + C*tmp
    print(ans)
    bef_ans = ans

Submission status: Accepted

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

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

A.sort()
S = 0
d = {}
for i in A:
    S += i
    if i in d:
        d[i] += 1
    else:
        d[i] = 1

Q = int(input())

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

Submission status: Accepted

Solution code:
n=(int)(input())
a=list(map(int, input().split(" ")))
times = (int)(input())
temp = [0 for i in range(10 ** 5 + 1)]
samu = sum(a)
for i in a:
    temp[i] += 1
for i in range(times):
    moto, saki = map(int, input().split(" "))
    samu += (saki - moto) * temp[moto]
    temp[saki] += temp[moto]
    temp[moto] = 0
    print(samu)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
d=Counter(A)
t_s=sum(A)
Q=int(input())
for __ in range(Q):
    a,b=list(map(int,input().split()))
    if d[a]!=0:
        curr_c=d[a]
        t_s-=a*(curr_c)
        t_s+=b*(curr_c)
        d[b]=d.get(b,0)+curr_c
        d[a]=0
    print(t_s)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
x=[0 for i in range(10**5+1)]
su=0
y=[0 for i in range(q)]
import copy
for i in range(n):
    su+=a[i]
    x[a[i]]+=1

for i in range(q):
    b,c=map(int,input().split())
    su+=(c-b)*x[b]
    y[i]=copy.deepcopy(su)
    
    x[c]+=x[b]
    x[b]=0
    
for i  in range(q):
    print(y[i])

Submission status: Accepted

Solution code:
n = int(input())
a = input().split()
q = int(input())
d = dict()
s = 0
for num in a:
  if num in d:
    d[num] += 1
  else:
    d[num] = 1
  s += int(num)
for i in range(q):
  B, C = input().split()
  if B in d:
    if C in d:
      d[C] += d[B]
    else:
      d[C] = d[B]
    s += (int(C)-int(B))*d[B]
    d[B] = 0
  print(s)

Submission status: Accepted

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

s = sum(a_s)
m = { a: 0 for a in a_s }

for a in a_s:
    m[a] += 1

for b, c in bc_s:
    nb = m.get(b, 0)
    s += nb * (c - b)
    print(s)
    m[b] = 0
    m[c] = nb + m.get(c, 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
element=[0]*(10**5)
total=sum(A)
for a in A:
    element[a-1]+=1
Q=int(input())
for q in range(Q):
    B,C=map(int,input().split())
    total+=element[B-1]*(C-B)
    if element[B-1]!=0:
        element[C-1]+=element[B-1]
        element[B-1]=0
    print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin


def main():
    input = lambda: stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [tuple(map(int, input().split())) for _ in [0] * Q]

    num = defaultdict(list)
    for i, a in enumerate(A):
        num[a].append(i)

    sum_a = sum(A)
    for b, c in BC:
        d = c - b
        sum_a += d * len(num[b])
        num[c] += num[b]
        del num[b]
        print(sum_a)


main()

Submission status: Accepted

Solution code:
n = int(input())
num_dict = {}
numbers = map(int,input().split())
last_sum = 0;
for val in numbers: 
    last_sum+=val
    if val in num_dict:
        num_dict[val]+=1
    else:
        num_dict[val]=1

q = int(input())
for i in range(0,q):
    b,c=map(int,input().split())
    if b in num_dict:
        last_sum += (c-b)*num_dict[b]
        if c in num_dict:
            num_dict[c]+=num_dict[b]
        else:
            num_dict[c]=num_dict[b]
        num_dict.pop(b,'ignore')

    
    print(last_sum)

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

Solution code:

N = int(input())
nums = {}

for a in map(int, input().split()):
    if a not in nums:
        nums[a] = 0
    nums[a] += 1

q = int(input())

csum = sum([k*v for k, v in nums.items()])

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

Submission status: Accepted

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


counts = [0] * 110000

for a in aes:
  counts[a] += 1

ans = 0
for i, c in enumerate(counts):
  ans += i * c

for i in range(q):
  p = counts[bs[i]]
  counts[bs[i]] = 0
  ans -= bs[i] * p
  counts[cs[i]] += p
  ans += cs[i] * p
  print(ans)

Submission status: Accepted

Solution code:
import collections

def A_sum(A):
  s = 0
  for i in A.items():
    s+=i[0]*i[1]
  return s

def A_rep(A,f,t):
  f_num = A.get(f)
  if f_num != None:
      A[t]=A.get(t,0) + f_num
      diff = f_num*(t-f)
      A.pop(f)
      return diff
  return 0

N = int(input())
A = collections.Counter(map(int,input().split()))
Q = int(input())
ans = A_sum(A)
for i in range(Q):
  b,c = map(int,input().split())
  diff = A_rep(A,b,c)
  if diff !=0:
    ans+=diff
  print(ans)

Submission status: Accepted

Solution code:
x = int(input())
ar = list(map(int, input().split()))
sum_val = sum(ar)

unique_val = dict()

for i in ar:
    if i in unique_val:
        unique_val[i] += 1
    else:
        unique_val[i] = 1

q = int(input())
while(q):
    a, b = map(int, input().split())
    if a in unique_val:
        value = (b-a)*unique_val[a]
        sum_val += value
        if b in unique_val:
            unique_val[b] = unique_val[b] + unique_val.pop(a)
        else:
            unique_val[b] = unique_val.pop(a)
        #print(unique_val)
        
    print(sum_val)
    q -= 1

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict
import numpy as np

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

d = Counter(A)
s = sum([k*v for k, v in d.items()])
for _ in range(Q):
  b, c = map(int, input().split())
  if b in d.keys():
    t = d.pop(b)
    if c in d.keys():
      d[c] += t
    else:
      d[c] = t
    s += t*(c-b)
  print(s)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque
def r():
    return int(input())
def rm():
    return map(int,input().split())
def rl():
    return list(map(int,input().split()))

'''D'''
n=r()
a=rl()
d=defaultdict(int)
for i in a:
    d[i]+=1
s=sum(a)
for i in range(r()):
    b,c=rm()
    m=d[b]
    s+=m*(c-b)
    d[c]+=m
    d[b]=0
    print(s)

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

cnt=[0]*(10**5+1)
for a in A:
  cnt[a]+=1
total=sum(A)
for b,c in BC:
  total+=(c-b)*cnt[b]
  cnt[c]+=cnt[b]
  cnt[b]=0
  print(total)

Submission status: Accepted

Solution code:
import math
data = input()
num = int(data)
o = input().rstrip().split(" ")
list =[]
for i in o:
    list.append(int(i))
p = input()
times = int(p)
ans = sum(list)
num_count=[0 for i in range(100001)]
for i in list:
    num_count[i] += 1
for i in range(times):
    B, C = map(int, input().split(" "))
    a = num_count[B]
    num_count[B] = 0
    num_count[C] += a
    ans += a*(C-B)
    print(ans)

Submission status: Accepted

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

d = {}
for i in range(N):
  if(A[i] not in d):
    d[A[i]] = 1
  else:
    d[A[i]] += 1
total = sum(A)
for i in range(Q):
  if(B[i] in d):
    num = d[B[i]]
    total += num*(C[i]-B[i])
    d.pop(B[i])
    if(C[i] in d):
      d[C[i]] += num
    else:
      d[C[i]] = num
  print(total)

Submission status: Accepted

Solution code:
n = input()
a = [int(i) for i in input().split()]
q = int(input())
bb = []
cc = []
for i in range(q):
    btmp, ctmp = [int(j) for j in input().split()]
    bb.append(btmp)
    cc.append(ctmp)


amap = {}
for i in a :
    if i not in amap :
        amap[i] = 1
    else:
        amap[i] += 1

atol = sum(a)

for b,c in zip(bb,cc):
    
    if b in amap:
        atol +=  (c - b) * amap[b]
    
        if c in amap :
            amap[c] += amap[b]
        else:
            amap[c] = amap[b]
        
        amap.pop(b)
        
    print(atol)

Submission status: Accepted

Solution code:
#!python3.8
# -*- coding: utf-8 -*-
# abc171/abc171_d
import sys
from collections import Counter

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [i2s() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))

def main():
    N = i2n()
    A = i2nn()
    sum_ = sum(A)
    cntr = Counter(A)
    Q = i2n()
    for _ in range(Q):
        B, C = i2nn()
        bn = cntr.pop(B, 0)
        sum_ += C * bn - B * bn
        cntr[C] += bn
        print(sum_)
    return

main()

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res

N=II()

MP={}
for i in LI():
    if not i in MP: MP[i] = 0
    MP[i] += 1

Q=II()

res = 0
for i, j in MP.items():
    res += i*j

arr = []
for _ in range(Q):
    B, C = LI()
    if not B in MP: MP[B] = 0
    if not C in MP: MP[C] = 0
    diff = MP[B]*C - MP[B]*B
    MP[C] += MP[B]
    MP[B] = 0
    res += diff
    arr.append(res)

for i in arr: print(i)

Submission status: Accepted

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

        ans=ans-g*(b-c)
        print(ans)
resolve()

Submission status: Accepted

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

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 = [list(i) for i in zip(*BC)]

sum = 0
size = 10 ** 5 + 1
list = [0] * size
for a in A:
    list[a] += 1
    sum += a

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

Submission status: Accepted

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

List = [0]*100000
for i in A:
  List[i-1] += 1
  ans += i

dic = {}
for i in range(100000):
  if List[i] != 0:
    dic[i+1] = List[i]



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

Submission status: Accepted

Solution code:
input()
As = [int(n) for n in input().split()]
# print(As)
count = {}
sum = 0
for A in As:
    pre = count.get(A, 0)
    count[A] = pre + 1
    sum += A
# print(count)
# print(sum)

Q = int(input())
for i in range(Q):
    B, C = (int(n) for n in input().split())
    B_count = count.pop(B, 0)
    sum += (C - B) * B_count
    count[C] = count.get(C, 0) + B_count
    print(sum)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
oper = [list(map(int, input().split())) for _ in range(q)]
dic = {}
for i in range(n):
    if a[i] in dic:
        dic[a[i]] += 1
    else:
        dic[a[i]] = 1
        
res = sum(a)

for i in range(q):
    b, c = oper[i]
    if b in dic:
        bCount = dic[b]
        del(dic[b])
        if c in dic:
            dic[c] += bCount
        else:
            dic[c] = bCount

        dif = c-b

        res += dif*bCount

    print(res)

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)
l = [0] * 10**6
for ai in a:
    l[ai-1] += 1

for i in range(q):
    s += (bc[i][1] - bc[i][0]) * l[bc[i][0]-1]
    l[bc[i][1]-1] += l[bc[i][0]-1]
    l[bc[i][0]-1] = 0
    print(s)

Submission status: Accepted

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

    d={}
    s=0
    for i in r(n):
        cu=a[i]

        if d.get(cu, None):
            d[cu]+=1
        else:
            d[cu]=1
        
        s+=cu
    
    for _ in r(q):
        bi, ci = map(int, input().split())
        diff=ci-bi

        if d.get(ci, None):
            d[ci]+=d.get(bi, 0)
        else:
            d[ci]=d.get(bi, 0)

        s+=diff * d.get(bi, 0)
        print(s)

        if d.get(bi, None):
            d[bi]=0


if __name__ == '__main__':
    t=1
    for _ in range(t):
        solve()

Submission status: Accepted

Solution code:
import collections

def calc_sum(c):
    sum_val = 0
    for key, val in c.items():
        sum_val += key * val
    return sum_val

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

actions = []

for i in range(Q):
    B, C = map(int, input().split())
    actions.append({'B':B, 'C':C})

c = collections.Counter(arr)
sum_val = calc_sum(c)

for i in range(Q):
    B = actions[i]['B']
    C = actions[i]['C']
    if B in c:
        c[C] += c[B]
        sum_val += c[B] * C - c[B] * B
        c.pop(B)

    print(sum_val)

Submission status: Accepted

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

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

    return ans

VALUE = [0 for i in range(100000)]

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

ANS = []
ANS.append(calc(VALUE))

for i in range(Q):
    VALUE[BC[i][1] - 1] += VALUE[BC[i][0] - 1]
    ANS.append(ANS[i] + (BC[i][1] - BC[i][0]) * VALUE[BC[i][0] - 1])
    VALUE[BC[i][0] - 1] = 0

for i in range(1, Q + 1):
    print(ANS[i])

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = list(map(int,input().split()))
q = int(input())
d = defaultdict(lambda: 0)
Sum = 0
for nums in a:
    d[nums] += 1
for keys in d:
        cnt = d[keys]
        keys = int(keys)
        Sum += keys*cnt
for i in range (q):
    b,c = map(int,input().split())
    d[c] += d[b]
    Sum += (c-b)*d[b]
    del d[b]
    print(Sum)

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_count = []
total = 0
for i in range(n):
  total += a[i]

count = collections.Counter(a)
for i in range(q):
  num = count[bc[i][0]]
  count[bc[i][0]] = 0
  count[bc[i][1]] += num
  total += (bc[i][1] - bc[i][0]) * num
  print(total)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
q=int(input())
dic=dict()
list_sum=sum(l)
for i in range(len(l)):
    if(l[i] not in dic.keys()):
        dic[l[i]]=1
    else:
        dic[l[i]]+=1
# print(dic)
s=list_sum
for i in range(q):
    b,c=map(int,input().split())
    # print(dic)
    if(b in dic and dic[b]!=0):
        s+=(c-b)*dic[b]
        if(c in dic):
            dic[c]+=dic[b]
            dic[b]=0
        else:
            dic[c]=dic[b]
            dic[b]=0
    
    print(s)
    # print(dic)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

res = 0

dct = defaultdict(int)
for _ in range(N):
  n = nums.pop()
  dct[n] += 1
  res += n

for _ in range(Q):
  B, C = map(int,input().split())
  if B in dct:
    n = dct.pop(B)
    res += (C - B) * n
    if C in dct:
      dct[C] += n
    else:
      dct[C] = n
  
  print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
bc = []
for _ in range(q):
    bc.append([int(i) for i in input().split()])

a_dict = {}
for x in a:
    if x in a_dict:
        a_dict[x] += 1
    else:
        a_dict[x] = 1

s = 0
for k, v in a_dict.items():
    s += k*v

for b, c in bc:
    if b in a_dict:
        s += (c-b) * a_dict[b]
        print(s)
        if c in a_dict:
            a_dict[c] += a_dict[b]
        else:
            a_dict[c] = a_dict[b]
        a_dict[b] = 0
        
    else:
        print(s)
        pass

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    N = int(input())
    A = input().split()
    counts = defaultdict(int)
    ans = 0
    for a in A:
        counts[a] += 1
        ans += int(a)
    Q = int(input())
    BC = []
    for _ in range(Q):
        BC.append(input().split())
    for b,c in BC:
        ans += (int(c)-int(b)) * counts[b]
        print(ans)
        counts[c] += counts[b]
        counts[b] = 0

if __name__ == '__main__':
    main()