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:
"""
NTC here
"""
 
 
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

profile = 0
pypy = 1
 
 
def iin(): return int(input())


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


def main():
    n = iin()
    a = lin()
    q = iin()
    dc = {}
    for i in a:
        try:
            dc[i] += 1
        except:
            dc[i] = 1
    sm = sum(a)
    for i in range(q):
        b, c= lin()
        if b in dc:
            sm += c*dc[b] -b*dc[b]
            try:
                dc[c] += dc[b]
            except:
                dc[c] = dc[b]
            dc.pop(b)
        print(sm)






    




                

        

 
 
 
 
 
 
# region fastio
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
if pypy:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
    input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
 
if __name__ == "__main__":
    if profile:
        import cProfile
        cProfile.run('main()')
    else:
        main()

Submission status: Accepted

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

change_pair = []
for i in range(Q):
    b, c = map(int, input().split())
    change_pair.append((b, c))

# Aの出現値毎に回数をカウント
counts = {}
total = 0
for a in A:
    if a in counts:
        counts[a] += 1
    else:
        counts[a] = 1
    total += a

# 置き換え毎に回数を移動
for b, c in change_pair:
    if b in counts:
        count = counts[b]
        counts[b] = 0
        total -= b * count
    else:
        count = 0
    if c in counts:
        counts[c] += count
    else:
        counts[c] = count
    total += c * count
    print(total)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import Counter
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    Q = int(readline())
    dd = Counter(A) 
    S = sum(A)
    
    for _ in range(Q):
        b, c = map(int, readline().split())
        dd[c] += dd[b]
        S = S - b*dd[b] + c*dd[b]
        dd[b] = 0
        print(S)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    bucket = [0] * (10 ** 5 + 1)
    sum = 0
    for i in A:
        bucket[i] += 1
        sum += i
    # print(bucket[0], bucket[1], bucket[2], bucket[3], bucket[4], bucket[5])
    
    for i in range(Q):  # B[i] -> C[i]
        b, c = B[i], C[i]
        num = bucket[b]
        sum += (c - b) * num
        bucket[b] = 0
        bucket[c] += num
        print(sum)
        # print(bucket[0], bucket[1], bucket[2], bucket[3], bucket[4], bucket[5])
    


    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)

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

BC = []
for _ in range(Q):
    b, c = map(int, input().split())
    BC.append([b, c])

C = Counter(A)
S = sum([k*v for k, v in C.items()])
for bc in BC:
    b = bc[0]
    c = bc[1]
    if b in C:
        bf = C[b]
        S += (c-b) * bf
        if c in C:
            C[c] += C[b]
            C[b] = 0
        else:
            C[c] = C[b]
            C[b] = 0
    print(S)

Submission status: Accepted

Solution code:
## coding: UTF-8

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

#print(N, A, Q, lq)


ans = sum(A)
num = [i for i in range(1, 10**5+10)]
#num = [i for i in range(1, 10000)]
d = {k: 0 for k in num}
#print(d)


for i in range(N):
    d[A[i]] += 1
#print(d)


for i in range(Q):
    query = lq[i]
    start = query[0]
    goal = query[1]
    n = d[start]
    ans -= start * n
    ans += goal * n
    d[start] = 0
    d[goal] += n
    print(ans)

Submission status: Accepted

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

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

q=int(input())
for i in range(q):
  a,b=map(int,input().split())
  dif=b-a
  if a not in d:
    d[a]=0
  sm+=(dif*d[a])
  print(sm)
  if b not in d:
    d[b]=0
  d[b]+=d[a]
  d[a]=0

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
q=int(input())
dic={i+1:0 for i in range(10**5)}
for a in A:
  dic[a]+=1

s=sum(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

nums_dict = defaultdict(int)
sum_nums = sum(nums)

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

M = int(input())

for i in range(M):
    original, replaced = map(int, input().split())

    if original not in nums_dict:
        print(sum_nums)
        continue

    total_change = (replaced - original) * nums_dict[original]
    sum_nums += total_change

    print(sum_nums)

    nums_dict[replaced] += nums_dict[original]
    del nums_dict[original]

Submission status: Accepted

Solution code:
import sys
n = int(sys.stdin.readline().rstrip("\n"))
s = 0
a = [0]*(10**6)
for z in sys.stdin.readline().rstrip("\n").split():
    z = int(z)
    a[z] += 1
    s += z
q = int(sys.stdin.readline().rstrip("\n"))
for i in range(q):
    b,c = map(int, sys.stdin.readline().rstrip("\n").split())
    d = c-b
    s += d*a[b]
    a[c] += a[b]
    a[b] = 0
    print(s)

Submission status: Accepted

Solution code:
import sys 
from collections import Counter

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
Q = int(sys.stdin.readline().strip())

ans = sum(A)
counter = Counter(A)
# print(counter)
query = []
for _ in range(Q):
    b, c = map(int, sys.stdin.readline().strip().split())
    ans = ans - counter[b] * b + counter[b] * c
    print(ans)
    if c not in counter:
        counter[c] = 0
    counter[c] += counter[b]
    counter[b] = 0

Submission status: Accepted

Solution code:
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    n=INT()
    a=LIST()
    q=INT()
    temp=sum(a)
    cnt=[0]*(10**5+1)
    for i in a:
        cnt[i]+=1
    
    for i in range(q):
        #print(cnt[:10])
        b,c=INTM()
        temp=temp+(c-b)*cnt[b]
        cnt[c]+=cnt[b]
        cnt[b]=0
        print(temp)

                
if __name__ == '__main__':
    do()

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter(arr)
total = sum(arr)

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

Submission status: Accepted

Solution code:
from collections import Counter

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

dic = Counter(A)

Q = int(input())

for _ in range(Q):
    b, c = map(int, input().split())
    if b in dic.keys():
        sumA += ((c-b)*dic[b])

        #変更後の数字は既にいる？
        if c in dic.keys():
            #個数を保持
            #bの個数をcに追加し、bを削除
            dic[c] += dic[b]
            del dic[b]
        else:
            dic[c] = dic[b]
            del dic[b]
        # print("C", C)
        
        
        
        # print(dic)
    # else:
    #     ans = sumA
    print(sumA)

Submission status: Accepted

Solution code:
from collections import Counter

N, *I = map(int, open(0).read().split())
A, Q, BC = I[:N], I[N], I[N + 1:]

C = Counter(A)
ans = sum(A)
for b, c in zip(*[iter(BC)] * 2):
    ans += (c - b) * C[b]
    C[c] += C[b]
    C[b] = 0
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
counter = Counter(A)
total = 0
for k,v in counter.items():
  total += k*v
Q = int(input())

for _ in range(Q):
  b,c = map(int,input().split())
  if b in counter:
    total -= b*counter[b]
    item = counter[b]
    del counter[b]
    if c in counter:
      counter[c] += item
      total += c*item
    else:
      counter[c] = item
      total += c*counter[c]
  
  print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

n=int(input())
a=[int(x) for x in input().rstrip().split()]
dp=[0 for i in range(10**5)]
q=int(input())

for i in a:
  dp[i-1]+=1

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
dict={}
for k in a:
    if k in dict:
        dict[k]+=1
    else:
        dict[k]=1

ans=0
for k,v in dict.items():
    ans+=k*v

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

Submission status: Accepted

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

A_sum = sum(A)
A_dict = {}

for a in A:
    if a not in A_dict:
        A_dict[a] = 0
    A_dict[a] += 1

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

for i in range(Q):
    b = B[i]
    c = C[i]
    if b not in A_dict:
        num = 0
    else:
        num = A_dict[b]
        A_dict[b] = 0
    print(A_sum - num*b + num*c)
    A_sum = A_sum - num*b + num*c
    if c not in A_dict:
        A_dict[c] = 0
    A_dict[c] += num

Submission status: Accepted

Solution code:
import collections


def resolve():
    n = int(input())
    targets = list(map(int, input().split()))
    q = int(input())
    ans = sum(targets)

    targets = collections.Counter(targets)

    for i in range(q):

        b, c = map(int, input().split())
        num_of_b = targets[b]
        targets.update({c: num_of_b})
        del targets[b]
        ans += (c-b)*num_of_b
        print(ans)

resolve()

Submission status: Accepted

Solution code:
from sys import stdin
from sys import setrecursionlimit
from collections import Counter
setrecursionlimit(10 ** 7)

n = int(input())
a = list(map(int,stdin.readline().rstrip().split()))
su = sum(a)

q = int(input())
cc = Counter(a)

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

Submission status: Accepted

Solution code:
#D
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
C=Counter(A)
ans=sum(A)

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

Submission status: Accepted

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

ans = sum(l)

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
N = int(readline())
A = list(map(int, readline().split()))

x = [0] * (10**5+5)
for a in A:
    x[a] += 1
s = sum(A)
Q = int(readline())
for _ in range(Q):
    b, c = map(int, readline().split())
    s += (c - b) * x[b]
    print(s)
    x[c] += x[b]
    x[b] = 0

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
counter = Counter(A)
ans = sum(A)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
import math
import bisect
from collections import deque
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int,input().split()))
q = int(input())

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

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

for ii in bc:
    [b,c] = ii
    if alis[b]!=0:
        ans+=(c-b)*alis[b]
        alis[b],alis[c] = 0,alis[b]+alis[c]
    #print(alis[0:5])
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
As = list(map(lambda x: int(x), input().split(" ")))
c = Counter(As)

sum_a = sum(As)

Q = int(input())
for _ in range(Q):
    B, C = map(lambda x: int(x), input().split(" "))
    change_count = c[B]
    sum_a -= change_count * B
    c[B] = 0
    sum_a += change_count * C

    if C in c:
        c[C] += change_count
    else:
        c[C] = change_count

    print(sum_a)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt=Counter(A)
total=sum(A)
for _ in range(q):
    b, c = map(int, input().strip().split())
    if b in cnt:
        total-=b*cnt[b]
        total+=c*cnt[b]
        cnt[c]+=cnt[b]
        del cnt[b]
    print(total)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
#map(int,input().split())
#int(x) for x in input().split()
#for _ in range(int(input())):
n=int(input())
l=[int(x) for x in input().split()]
q=int(input())
d={}
for i in range(len(l)):
	if l[i] in d:
		d[l[i]]+=1
	else:
		d[l[i]]=1
s=sum(l)
for i in range(q):
	a,b=map(int,input().split())
	if a==b:
		print(s)
		continue
	if a not in d:
		d[a]=0
	s=(s-d[a]*a+b*d[a])
	print(s)
	if b in d:
		d[b]+=d[a]
	else:
		d[b]=d[a]
	d[a]=0

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
m = {}
total = 0
for i, x in enumerate(arr):
    if m.get(x):
        m[x] += 1
    else:
        m[x] = 1
    total += x
for _ in range(int(input())):
    b, c = [int(x) for x in input().split()]
    if m.get(c):
        q = 1
    else:
        m[c] = 0
    if m.get(b):
        q = 1
    else:
        m[b] = 0
    total = total - (b*m[b]) + (c*m[b])
    m[c] += m[b]
    m[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()))
    D = Counter(A)
    Q = int(input())
    T = sum(A)
    for i in range(Q):
        b, c = map(int, input().split())
        if b in D.keys():
            T += (c-b) * D[b]
            D[c] += D[b]
            D[b] = 0
        print(T)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:


import sys
import math
import itertools
import collections

def solve(N:int,A:list,Q:int,B:list,C:list) -> None:
    total = sum(A)
    A = [str(a) for a in A]
    counter = collections.Counter(A)
    for b,c in zip(B,C):
        number = counter[str(b)]
        total = total - (number * b) + (number * c)
        print(total)
        counter[str(b)] = 0
        counter[str(c)] += number

def main():
    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)
    # solve()
    solve(N,A,Q,B,C)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
dic = {}
A = list(map(int,input().split()))
for item in A:
  if item in dic:
    dic[item] += 1
  else:
    dic[item] = 1
Q = int(input())
total = sum(A)
for _ in range(Q):
  b,c = map(int,input().split())
  if b in dic:
    gap = (c-b)*dic[b]
    total += gap
    if c in dic:
      dic[c] += dic[b]
      dic[b] = 0
    else:
      dic[c] = dic[b]
      del dic[b]
  print(total)

Submission status: Accepted

Solution code:
def main():
	import sys
	input=sys.stdin.readline
	n=int(input())
	num=[0]*(10**5+2)
	a=list(map(int,input().split()))
	for x in a:
		num[x-1]+=1
	q=int(input())
	ans=0
	for i in range(len(num)):
		ans+=(i+1)*num[i]
	for i in range(q):
		b,c=map(int,input().split())
		ans+=num[b-1]*(c-b)
		num[c-1]+=num[b-1]
		num[b-1]=0
		print(ans)
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
N = input().strip() ;

arr = list ( map ( int , input().strip().split(" ") ) ) ; 

dic = {} ;
for v in arr :
	d = dic[v] if v in dic else 0;
	dic[v] = d + 1; 

Q = int ( input().strip() ) ;
s0 = sum ( arr ) ;
for zz in range( Q  ) :
	b , c = map ( int , input().strip().split(" ") ) ;
	

	if not b in dic :
		pass ;
	else :
		s0 -= b * dic[b] ;
		s0 += c * dic[b] ;

		d = dic[c] if c in dic else 0 ;
		dic[c] = dic[b] + d ;
		del dic[b] ;
	print (  s0 ) ;

Submission status: Accepted

Solution code:
from collections import Counter

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

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

q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    if b not in d.keys():
        print(s)
        continue
    cc = 0
    s = s + (c-b) * d[b]
    print(s)
    if c in d.keys():
        cc = d[c]
    d[c] = cc + d[b]
    del d[b]

Submission status: Accepted

Solution code:
n=int(input())
arr = list(map(int,input().split()))
som = sum(arr)
q=int(input())
freq = {}
for i in range(n):
    if arr[i] in freq:
        freq[arr[i]]+=1
    else:
        freq[arr[i]]=1
for _ in range(q):
    b,c=map(int,input().split())
    if b in freq:
        som = som + freq[b]*(c-b)
        if c in freq:
            freq[c] += freq[b]
        else:
            freq[c] = freq[b]
        freq[b]=0
        print(som)
    else:
        print(som)

Submission status: Accepted

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

ans = sum(A)
numbers_a = [0] * (10**5+10)

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

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

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n=I()[0];arr=I();q=I()[0];
cnt={};
for i in arr:cnt[i]=0;
for i in arr:cnt[i]+=1;
s=sum(arr)
while(q):
  q-=1;b,c=I();
  if(b not in cnt or not cnt[b]):print(s);continue;
  s-=(cnt[b]*b);s+=(cnt[b]*c);
  if(c not in cnt):cnt[c]=0;
  cnt[c]+=cnt[b];cnt[b]=0;
  print(s)

Submission status: Accepted

Solution code:
n = int(input())
lisA = list(map(int,input().split()))
dic  = {}
for item in lisA:
    if item in dic:
        dic[item] += 1
    else:
        dic[item] = 1
q = int(input())
ans = sum(lisA)
for i in range(q):
    b,c = map(int,input().split())
    if b not in dic:
        print(ans)
    else:
        tmp = dic[b]
        if c in dic:
            dic[c] += dic[b]
        else:
            dic[c] = dic[b]
        dic[b] = 0
        if b > c:
            ans -= (b-c) * tmp
        else:
            ans += (c-b) * tmp
        print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

CA = Counter(A)

s = sum(A)

for b, c in BC:
  heri = CA[b] * b
  hue = CA[b] * c
  s += (- heri + hue)
  CA[c] += CA[b]
  CA[b] = 0
  print(s)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

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

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7


#############
# Main Code #
#############

N = getN()
A = getList()
Q = getN()
B = [getNM() for i in range(Q)]

num = [0] * (10 ** 5 + 10)
for i in range(N):
    num[A[i]] += 1

ans = sum(A)
for i in range(Q):
    bef, aft = B[i]
    bef_time = num[bef]
    num[bef] = 0
    ans += bef_time * (aft - bef)
    num[aft] += bef_time
    print(ans)

Submission status: Accepted

Solution code:
import collections
def main():
    n = int(input())
    A=[int(i) for i in input().split()]
    dd = collections.defaultdict(int)
    k = sum(A)
    res = []
    q = int(input())
    for i in A:
        dd[i]+=1
    for i in range(q):
        b,c=map(int, input().split())
        k = k - (b*dd[b])
        k = k + ((c)*(dd[b]))
        dd[c]=dd[c]+dd[b]
        dd[b]=0

        res.append(k)
    for i in res:
        print(i)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
from collections import deque
from collections import defaultdict
import heapq
import collections
import itertools
import bisect


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


def z():
    return int(input())


def S():
    return input()


def C(line):
    return [input() for _ in range(line)]


N = z()
A = zz()
Q = z()
B, C = [], []
for i in range(Q):
    b, c = zz()
    B.append(b)
    C.append(c)
num_lis = [0]*(10**5 + 1)
# print(len(num_lis))
for a in A:
    num_lis[a] += 1
sum_A = sum(A)
# print(len(num_lis))
for i in range(Q):
    b, c = B[i], C[i]

    sum_A = sum_A + (num_lis[b])*c - num_lis[b]*b
    # print('b', b, 'c', c)
    # print(num_lis)
    # print(num_lis[c])
    num_lis[c] = num_lis[c] + num_lis[b]
    # print(num_lis[c])
    num_lis[b] = 0
    # print(num_lis)
    # print("==========")
    print(sum_A)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
bcs = []
for i in range(Q):
  j,k = map(int,input().split())
  bcs.append([j,k])
s = sum(A)
cnts = [0]*100000
for a in A:
  cnts[a-1]+=1
for b,c in bcs:
  t = cnts[b-1]
  s -= t * b
  cnts[b-1]=0
  cnts[c-1]+=t
  s += t*c 
  print(s)

Submission status: Accepted

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from collections import defaultdict

def resolve():
    it = map(int, sys.stdin.read().split())
    N = next(it)

    d1 = defaultdict(int)
    sum1 = 0
    for i in range(N):
        v = next(it)
        sum1 += v
        d1[v] += 1

    Q = next(it)
    ans = []
    for bi, ci in zip(it, it):
        cnt = d1[bi]
        sum1 += (ci-bi)*cnt
        d1[bi] = 0
        d1[ci] += cnt
        ans.append(sum1)

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()