Problem:


Score : 400 points

Problem Statement

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

You will now successively do the following Q operations:

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

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

Constraints

All values in input are integers.

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

 B_{i} \neq C_{i} 

Input

Input is given from Standard Input in the following format:

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

Output

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

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

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

Sample Input 1

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

Sample Output 1

11
12
16

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

After each operation, it becomes the following:

2, 2, 3, 4

2, 2, 4, 4

4, 4, 4, 4

Sample Input 2

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

Sample Output 2

8
4
4

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

Sample Input 3

2
1 2
3
1 100
2 100
100 1000

Sample Output 3

102
200
2000



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


Sample output:
11
12
16

Submission status: Accepted

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

Submission status: Accepted

Solution code:
'''
参考
https://drken1215.hatenablog.com/entry/2020/06/21/224900
'''
N = int(input())
A = list(map(int, input().split()))

INF = 10 ** 5
cnt = [0] * (INF+1)

Q = int(input())
BC = []

for _ in range(Q):
    BC.append(list(map(int, input().split())))

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 sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    L = [list(map(int, input().split())) for i in range(Q)]
    Ac = Counter(A)
    ans = 0
    for k, v in Ac.items():
        ans += int(k)*v

    for b,c in L:
        ans -= b*Ac[b]
        ans += c*Ac[b]
        Ac[c] += Ac[b]
        Ac[b] = 0
        print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n0 = int(1e5)+1
x = [0]*n0

n = int(input())
a0 = list(map(int,input().split()))
q = int(input())
bcs = []
for i in range(q):
    bcs.append(list(map(int,input().split())))

for a in a0:
    x[a] += 1
sum0 = sum(a0)

for bc in bcs:
    sum0 = sum0 + bc[1]*x[bc[0]] - bc[0]*x[bc[0]]
    x[bc[1]] += x[bc[0]]
    x[bc[0]] = 0
    print(sum0)

Submission status: Accepted

Solution code:
def solve(ls1, ls2):
    s = sum(ls1)
    m = {}
    for a in ls1:
        if not a in m:
            m[a] = 0
        m[a] += 1

    result = []
    for b, c in ls2:
        if not b in m:
            result.append(s)
            continue
        if not c in m:
            m[c] = 0
        s += (c - b) * m[b]
        m[c] += m[b]
        m[b] = 0
        result.append(s)
    return result


def main(istr, ostr):
    (n,) = list(map(int, istr.readline().strip().split()))
    ls1 = list(map(int, istr.readline().strip().split()))
    (q,) = list(map(int, istr.readline().strip().split()))
    ls2 = [0] * q
    for i in range(q):
        ls2[i] = list(map(int, istr.readline().strip().split()))
    result = solve(ls1, ls2)
    print(*result, sep="\n", file=ostr)


if __name__ == "__main__":
    import sys

    main(sys.stdin, sys.stdout)

Submission status: Accepted

Solution code:
import sys
import numpy as np
from math import ceil as C, floor as F
from collections import defaultdict as D
from functools import reduce as R

ALP = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
alp = 'abcdefghijklmnopqrstuvwxyz'
def _X(): return sys.stdin.readline().rstrip().split(' ')
def _S(ss): return tuple(ss) if len(ss) > 1 else ss[0]
def S(): return _S(_X())
def _Ss(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Ss(): return _Ss(S())
def _I(ss): return tuple([int(s) for s in ss]) if isinstance(ss, tuple) else int(ss)
def I(): return _I(S())
def _Is(ss): return list(ss) if isinstance(ss, tuple) else [ss]
def Is(): return _Is(I())

_ = I()
xs = Is()
 
sss = 0
count = D(int)
for x in xs:
  sss += x
  count[x] += 1
  
q = I()
for _ in range(q):
  b, c = I()
  sss += (c - b) * count[b]
  print(sss)
  count[c] += count[b]
  count[b] = 0

Submission status: Accepted

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
Q = I()
BC = [LI() for _ in range(Q)]

sum_A = sum(A)
c = collections.Counter(A)

for pair in BC:
    num_from = pair[0]
    num_to = pair[1]
    if num_from in c:
        diff = (num_to - num_from) * c[num_from]
        sum_A += diff
        print(sum_A)
        c[num_to] += c[num_from]
        c[num_from]=0
    else:
        print(sum_A)

Submission status: Accepted

Solution code:
MAX = 10**5
N = int(input())
A = list(map(int, input().split()))

numlist = [0] * (MAX+1)
for i in range(N):
  numlist[A[i]] += 1
sumA = sum(A)
  
Q = int(input())
for i in range(Q):
  b, c = map(int, input().split())
  bcount = numlist[b]
  numlist[b] = 0
  numlist[c] += bcount
  sumA = sumA - bcount*b + bcount*c
  print(sumA)

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int, input().split()))
defo = sum(a)
default = [0]*100001
for i in a:
  default[i]+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
S=0
B=[0]*(10**5+1)
for i in A:
    S+=i
    B[i]+=1  #Bは要素数管理
Q=int(input())
C=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    S=S+(C[i][1]-C[i][0])*B[C[i][0]]
    B[C[i][1]]=B[C[i][0]]+B[C[i][1]]
    B[C[i][0]]=0
    print(S)

Submission status: Accepted

Solution code:
n = int(input())

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

s = sum(A)

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

for i in range(n):
  L[A[i]] += 1

q = int(input())

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

Submission status: Accepted

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

s = sum(a)

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

ans = []
for i in range(q):
    b, c = map(int, input().split())
    nb = arr[b]
    bc = arr[c]
    s -= b * nb
    s += c * nb
    arr[b] = 0
    arr[c] += nb
    ans.append(s)

for i in range(q):
    print(ans[i])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter


def solve(string):
    n, *aqbc = map(int, string.split())
    a, _, bc = aqbc[:n], aqbc[n], aqbc[n + 1:]
    s = sum(a)
    t = Counter(a)
    ans = []
    for b, c in zip(*[iter(bc)] * 2):
        if b not in t.keys():
            ans.append(s)
            continue
        if c in t.keys():
            t[c] += t[b]
        else:
            t[c] = t[b]
        s += (c - b) * t[b]
        del t[b]
        ans.append(s)
    return "\n".join(map(str, ans))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))

Submission status: Accepted

Solution code:
n=int(input())
ar=list(map(int,input().split()))
di={}
for i in ar:
    di[i]=di.get(i,0)+1
sm=sum(ar)
q=int(input())
for i in range(q):
    b,c=map(int,input().split())
    if(b not in di):
        print(sm)
    elif(b in di):
        x=di[b]
        del di[b]
        if(c in di):
            di[c]+=x
        else:
            di[c]=x
        s=0
        s=sm-(b*x)+(x*c)
        sm=s
        print(s)

Submission status: Accepted

Solution code:
#template
def inputlist(): return [int(j) for j in input().split()]
#template
from collections import Counter
N = int(input())
A = inputlist()
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i],C[i] = inputlist()
A_sum = sum(A)
dic = Counter(A)
for i in range(Q):
    A_sum += (C[i]-B[i])*dic[B[i]]
    print(A_sum)
    dic[C[i]] += dic[B[i]]
    dic[B[i]] = 0

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)

sam = sum(A)
baketu = [0]*(100001)
for a in A:
    baketu[a] += 1

for q in range(Q):
    sam = sam + baketu[B[q]] * (C[q] - B[q])
    baketu[C[q]] += baketu[B[q]]
    baketu[B[q]] = 0
    #print(baketu)
    print(sam)

Submission status: Accepted

Solution code:
li = [0]*(10**5+1)

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

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

ans = []
Q = int(input())
for i in range(Q):
    B,C = [int(zz) for zz in input().split()]
    p += (C-B)*li[B]
    li[C] += li[B]
    li[B] = 0
    ans.append(p)

[print(i) for i in ans]

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def SUM(num_List):
    answer = 0
    for i, num in enumerate(num_List):
        answer += num*i
    return answer

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = list()
C = list()
start = True

num_List = [0 for x in range(100001)]

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

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

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

    if start == True:
        num_List[c] = num_List[c] + num_List[b]
        num_List[b] = 0
        answer = SUM(num_List)
        start = False
        
    else:
        answer = answer + num_List[b]*(c-b)
        num_List[c] = num_List[c] + num_List[b]
        num_List[b] = 0

    print(answer)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
arr = list(map(int, input().split()))
summ = sum(arr)
val = Counter(arr)
Q = int(input())
for q in range(Q):
    B, C = list(map(int, input().split()))
    summ = summ + C * val[B] - B * val[B]
    val[C] += val[B]
    val[B] = 0
    print(summ)

Submission status: Accepted

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

m = 10**5+1
nums = [0]*m
ans = 0
for i in a:
  nums[i] += 1
  ans += i
  
for _ in range(q):
  b,c = map(int, input().split())
  ans -= b*nums[b]
  ans += c*nums[b]
  nums[c] += nums[b]
  nums[b] = 0
  print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
input=stdin.readline
input()
a=list(map(int,input().split()))
ans=sum(a)
b=[0]*(10**5+1)
for i in a:
  b[i]+=1
c=int(input())
for i in range(c):
  n,m=map(int,input().split())
  if b[n]>0:
    x=b[n]
    if x>0:
      b[m]+=x
      b[n]=0
      ans+=(m-n)*x
  print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n=int(input())
a=list(map(int,input().split()))
w=int(input())
c=[]
for i in range(w):
    c.append(list(map(int,input().split())))

b=[0]*10**5
for i in range(n):
    b[a[i]-1]+=1
ans=sum(a)
for i in range(w):
    ans=ans+b[c[i][0]-1]*(c[i][1]-c[i][0])
    cnt=b[c[i][0]-1]
    b[c[i][1]-1]+=cnt
    b[c[i][0]-1]=0
    #print(b)
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
def solve():
  N = int(input())
  A = list(map(int, input().split()))
  c = Counter(A)
  Q = int(input())
  ans = [0]*Q
  total = sum(A)
  for i in range(Q):
    x,y = map(int, input().split())
    total += c[x]*(y-x)
    c[y] += c[x]
    c[x] = 0
    ans[i] = total
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
tot = sum(A)
D = {}
for i in range(N):
    a = A[i]
    if a not in D:
        D[a] = 0
    D[a] += 1
Q = int(input())
for _ in range(Q):
    b,c = map(int,input().split())
    if b not in D:
        print(tot)
    else:
        d = c-b
        if c in D:
            n = D[b]
            D[c] += D[b]
            del D[b]
        else:
            n = D[b]
            D[c] = D[b]
            del D[b]
        tot += n*d
        print(tot)

Submission status: Accepted

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

num_cnt = {}
c_sum = 0
for a in al:
    num_cnt.setdefault(a,0)
    num_cnt[a] += 1
    c_sum += a

ans = []
q = int(input())

for _ in range(q):
    b,c = map(int, input().split())
    num_cnt.setdefault(b,0)
    num_cnt.setdefault(c,0)
    diff = num_cnt[b]*c - num_cnt[b]*b

    num_cnt[c] += num_cnt[b]
    num_cnt[b] = 0
    c_sum += diff
    ans.append(c_sum)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
a = Counter(A)
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]

ans = sum(A)
for b,c in bc:
    ans -= b*a[b]
    ans += c*a[b]
    if b in a:
        if c in a: a[c] += a[b]
        else: a[c] = a[b]
        a.pop(b)
    print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [tuple(map(int,input().split())) for i in range(Q)]
from collections import Counter
ctr = Counter(A)
sm = sum(A)

ans = []
for b,c in BC:
    n = ctr[b]
    sm -= n * b
    sm += n * c
    ctr[b] -= n
    ctr[c] += n
    ans.append(sm)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
q = I()
sumA = sum(A)
C = Counter(A)
for i in range(q):
    b,c = readInts()
    sumA -= b * C[b]
    sumA += c * C[b]
    C[c] += C[b]
    C[b] = 0
    print(sumA)

Submission status: Accepted

Solution code:
n=int(input())
a = list(map(int,input().split()))
q=int(input())
bc = [list(map(int, input().split())) for l in range(q)]
cnt=[0]*100001
Sum=0
for i in range(n):
  cnt[a[i]]+=1
  Sum+=a[i]
for i in range(q):
  Sum+=(bc[i][1]-bc[i][0])*cnt[bc[i][0]]                           
  cnt[bc[i][1]]+=cnt[bc[i][0]]
  cnt[bc[i][0]]=0
  print(Sum)

Submission status: Accepted

Solution code:
import sys
import numpy as np

input = sys.stdin.readline

def minus(a):
    return int(a)-1

M = 10**5
N = int(input())
A = list(map(minus, input().split()))
Q = int(input())


def solve():
    hist = list(np.histogram(A, M, (0, M))[0].astype(int))
    cur = sum(A) + N
    for _ in range(Q):
        b, c = map(minus, input().split())
        dh = hist[b]
        cur += dh*(c-b)
        hist[b] -= dh
        hist[c] += dh
        print(cur)

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
ini = lambda : int(input())
inm = lambda : map(int,input().split())
inl = lambda : list(map(int,input().split()))
gcd = lambda x,y : gcd(y,x%y) if x%y else y
nom = [0] * (10**5+1)
n = ini()
a = inl()
ans = sum(a)
for i in a:
        nom[i] += 1
q = ini()
for i in range(q):
        b,c = inm()
        d = c-b
        ans += nom[b] * d
        print(ans)
        nom[c] += nom[b]
        nom[b] = 0

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

count = collections.defaultdict(lambda: 0)
current = 0
for a in A:
  count[a] += 1
  current += a

for b, c in zip(B,C):
  current += (c - b) * count[b]
  print(current)
  count[c] += count[b]
  del count[b]

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    n = int(readline().rstrip())
    A = list(map(int, readline().rstrip().split()))
    counter = collections.Counter(A)
    q = int(readline().rstrip())
    BCList = [list(map(int, readline().rstrip().split())) for _ in range(q)]
    aList = [0] * (10**5 + 10)
    sumA = sum(A)
    for i in range(n):
        aList[A[i] - 1] += 1

    for i in range(q):
        b, c = BCList[i][0], BCList[i][1]
        if aList[b - 1] == 0:
            print(sumA)
            continue
        sumA += (c - b) * aList[b - 1]
        aList[c - 1] += aList[b - 1]
        aList[b - 1] = 0
        print(sumA)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]
dic = {}
for i in range(n):
  key = lst[i]
  if key not in dic:
    dic[key] = 0
  dic[key] += 1
#print(dic)
sum = 0
for key, value in dic.items():
  sum += key * value

m = int(input())
for _ in range(m):
  lst_s = list(map(int, input().split()))
  number = dic.get(lst_s[0])
  if number is not None:
    if lst_s[1] in dic:
      dic[lst_s[1]] += number
    else:
      dic[lst_s[1]] = number
    sum += lst_s[1] * number
    sum -= lst_s[0] * number
    dic.pop(lst_s[0])
  print(sum)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())

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

counter = Counter(A)
sum_res = sum(A)
#print(sum_res,counter)
for _ in range(Q):
    bf,af = map(int,input().split())
    sum_res -= bf*counter[bf]
    sum_res += af*counter[bf]
    
    counter[af] += counter[bf]
    counter[bf] = 0
    
    print(sum_res)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
q = int(input())
lst = [0] * q
for i in range(q):
    lst[i] = list(map(int, input().split()))
s = sum(A)
num = [0] * 10**5
for i in A:
    num[i-1] += 1
for i in range(q):
    s += num[lst[i][0]-1] * (lst[i][1] - lst[i][0])
    num[lst[i][1]-1] += num[lst[i][0]-1]
    num[lst[i][0]-1] = 0
    print(s)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

    ans = sum(a)
    for b, c in BC:
        if a[b] == 0:
            print(ans)
            continue
        move = a[b] // b
        a[b] = 0
        a[c] += c * move
        ans += (c - b) * move
        print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque

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

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

m = sum([k*v for (k,v) in d.items()])

q = int(input())

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

    if b in d:
        m += (c - b)*d[b]

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

        d[b] = 0

    print(m)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
freq = [0]*(10**5+1)

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

Submission status: Accepted

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

num_sum = sum(A)
B = [0]*(10**5+1)

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


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

Submission status: Accepted

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

Submission status: Accepted

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

dictA = {}
for i in arr:
    if dictA.get(i): dictA[i] += 1
    else: dictA[i] = 1

summ = sum(arr)

for i in range(q):
    b, c = list(map(int, input().split()))
    if dictA.get(b):
        summ = summ - (dictA[b]*b) + (dictA[b]*c)
        if dictA.get(c): dictA[c] += dictA[b]
        else: dictA[c] = dictA[b]
        del dictA[b]
    print(summ)

Submission status: Accepted

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

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

AllSum=sum(A)

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

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

Submission status: Accepted

Solution code:

from collections import Counter

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

ctr = Counter(X)
ans = sum(X)
for b, c in Y:
    n = ctr[b]
    ctr[b] = 0
    ctr[c] += n
    ans = ans - b * n + c * n
    print(ans)

Submission status: Accepted

Solution code:

def sum_dict(d):
    num = 0
    for k, v in d.items():
        num += k * v
    return num


def create_dict(A):
    d = {}
    for a in A:
        if d.get(a) is None:
            d[a] = 1
        else:
            d[a] += 1
    return d


if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(tuple(map(int, input().split())))

    d = create_dict(A)

    ans = sum_dict(d)
    for b, c in BC:
        db = d.get(b)
        if db is None:
            db = 0
        if d.get(c) is None:
            d[c] = 0
        d[c] += db
        d[b] = 0

        ans += (c - b) * db
        print(ans)

Submission status: Accepted

Solution code:
N=int(input())
array=[int(x) for x in input().split()]
dict={}
for i in array:
	if i in dict:
		dict[i]+=1
	else:
		dict[i]=1
total=sum(array)
for i in range(int(input())):
	A,B=[int(x) for x in input().split()]
	if A not in dict:
		dict[A]=0
	if B not in dict:
		dict[B]=0
	total=total-A*dict[A]+B*(dict[A])
	dict[B]=dict[B]+dict[A]
	dict[A]=0
	print(total)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

A_dict = defaultdict(int)
for a in A:
    A_dict[a] += 1

A_sum = sum(A)
for b, c in zip(B, C):
    n = A_dict[b]
    A_dict[b] = 0
    A_dict[c] += n
    A_sum += (c - b) * n
    print(A_sum)

Submission status: Accepted

Solution code:
n = int(input())
A = [0] * (10**5+1)

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

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

m = int(input())

sum_a = sum(B)

for _ in range(m):
    a, b = map(int, input().split())
    sum_a = sum_a + (b - a) * A[a]
    A[b] += A[a]
    A[a] = 0
    print(sum_a)

Submission status: Accepted

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

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

    maxA=max(A)
    maxC=max(C)
    if maxA>=maxC:
        m=maxA
    else:
        m=maxC
    dp=[0 for i in range(m+1)]

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

    res=sum(A)


    for _ in range(Q):
        i=B[_]
        j=C[_]

        res-=dp[i]*i
        dp[j] += dp[i]
        res+=j*dp[i]
        dp[i]=0
        print(res)

if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b


def sum_of_arithmetic_progression(s, d, n):
    return n * (2 * s + (n - 1) * d) // 2


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


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

    ans = 0
    d = defaultdict(int)
    for a in A:
        d[a] += 1
        ans += a

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

        if d[B] != 0:
            ans -= B * d[B]
            ans += C * d[B]

        d[C] += d[B]
        d[B] = 0

        print(ans)


def main():
    solve()


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    As = list(map(int, input().split()))
    As_Count = [0] * (10**5+1)
    q = int(input())
    bcs = [list(map(int, input().split())) for _ in range(q)]
    for A in As:
        As_Count[A] += 1
    ans = sum(As)
    for b, c in bcs:
        ans -= As_Count[b] * b
        ans += c * As_Count[b]
        As_Count[c] += As_Count[b]
        As_Count[b] = 0
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(input().split())
a=collections.Counter(A)
A=[int(i) for i in A]
S=sum(A)
Q=int(input())
for i in range(Q):
    B,C=input().split()
    if B in a:
        b=a[B]
        S-=int(B)*b
        S+=int(C)*b
        del a[B]
        if C in a:
            a[C]+=b
        else:
            a[C]=b
    print(S)

Submission status: Accepted

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

    q = int(input())
    num_table = [0] * 100010

    for ai in a:
        num_table[ai] += 1

    ans = sum(a)

    for _ in range(q):
        bi, ci = map(int, input().split())
        ans += num_table[bi] * (ci - bi)
        num_table[ci] += num_table[bi]
        num_table[bi] = 0
        print(ans)
        
resolve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
S = sum(A)
NUM = [0] * 100005
for a in A:
    NUM[a] += 1
for k in range(Q):
    S += (C[k]-B[k]) * (NUM[B[k]])
    NUM[C[k]] += NUM[B[k]]
    NUM[B[k]] = 0
    print(S)

Submission status: Accepted

Solution code:
def main():
    N = int(input().strip())
    A = [int(_a) for _a in input().strip().split()]
    Q = int(input().strip())
    BCS = []
    for i in range(Q):
        BCS.append([int(_bc) for _bc in input().strip().split()])

    Amap = {}
    for a in A:
        if a not in Amap:
            Amap[a] = 0
        Amap[a] += 1

    total = 0
    for k,v in Amap.items():
        total += (k*v)

    for bc in BCS:
        b = bc[0]
        c = bc[1]
        if b in Amap:
            num = Amap[b]

            del Amap[b]
            if c not in Amap:
                Amap[c] = 0
            Amap[c] += num

            total = total + num*c - num*b

        print(total)

main()