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:
def main():

    N = int(input())
    A = list(map(int, input().split()))
    d = dict()
    for v in A: d[v] = d.get(v, 0) + 1
    ans = sum(A)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
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:
    if ctr[b] == 0:
        ans.append(sm)
        continue
    sm += (c-b) * ctr[b]
    ctr[c] += ctr[b]
    ctr[b] = 0
    ans.append(sm)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin, stdout
import heapq
import cProfile
from collections import Counter, defaultdict, deque
from functools import reduce
import math


def get_int():
    return int(stdin.readline().strip())


def get_tuple():
    return map(int, stdin.readline().split())


def get_list():
    return list(map(int, stdin.readline().split()))


def solve():
    return

def main():
    n = get_int()
    ls = get_list()
    q = int(input())
    total = sum(ls)
    freq_dic = Counter(ls)
    for i in range(q):
        a,b = get_tuple()
        x = freq_dic[a]
        freq_dic[a] -= x
        freq_dic[b] += x
        total -= a*x
        total += b*x
        print(total)

TestCases = False

if TestCases:
    for i in range(get_int()):
        main()
else:
    main()

Submission status: Accepted

Solution code:
from collections import Counter
def resolve():
    N = int(input())
    A = list(map(int,input().split()))
    Q = int(input())
    tbl = [0] * 1000000
    for i in A:
        tbl[i] +=1
    sm = sum(A)
    for i in range(Q):
        B,C = map(int,input().split())
        tmp = tbl[B]
        sm -= B * tmp
        sm += C * tmp
        tbl[C] += tmp        
        tbl[B]=0
        print(sm)


resolve()

Submission status: Accepted

Solution code:
n=int(input())
arr=list(map(int,input().split()))
s=0
d={}
for i in arr:
    if i in d:
        d[i]+=1
    else:
        d[i]=1
    s+=i
for i in range(int(input())):
    a,b=map(int,input().split())
    if a in d:
        s=s-a*d[a]+b*d[a]
    if b in d and a in d:
        d[b]+=d[a]
    else:
        if a in d:
            d[b]=d[a]
    d[a] = 0
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
m = {}
a = [int(i) for i in input().split()]
for x in a:
    m[x] = 0

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

s = sum(a)
for i in range(int(input())):
    b, c=  map(int, input().split())
    if b in m:
        s -= m[b]*b
        s += m[b]*c
        if c in m:
            m[c] += m[b]
        else:
            m[c] = m[b]
        m[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())
bc = [list(map(int, input().split())) for _ in range(Q)]
ca = Counter(A)

s = sum(A)
for b, c in bc:
  tmp = ca[b]
  s = s - tmp*b + tmp*c
  ca[c] += ca[b]
  ca[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())

S = sum(A)
cntA = Counter(A)

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

    print(S)

Submission status: Accepted

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

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

    s += memo * (c - b)
    print(s)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
# from fractions import gcd

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
A = list(map(int, input().split()))
count = Counter(A)
q = int(input())
B = [list(map(int, input().split())) for i in range(q)]

s = sum(A)
for b, c in B:
    num = count[b]
    s += (c - b)*num
    count[c] += num
    count[b] = 0
    print(s)

Submission status: Accepted

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

Submission status: Accepted

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

totalSum = 0
numMap = {}
for a in listA:
    totalSum+=a
    if a in numMap:
        numMap[a]+=1
    else:
        numMap[a]=1

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

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


n = inp()
a = inpl()
data = collections.defaultdict(int)
for i in range(n):
    data[a[i]] += 1
q = inp()
ans = 0
for key, value in data.items():
    ans += key * value
for i in range(q):
    b, c = inpl()
    ans += (c - b) * data[b]
    data[c] += data[b]
    data[b] = 0
    print(ans)

Submission status: Accepted

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

import collections


def process_queries(ds, queries):
    table = collections.Counter(ds)
    s = sum(ds)
    for b, c in queries:
        table[c] += table[b]
        s += (c - b) * table[b]
        table[b] = 0
        yield s


def main():
    n = int(input())
    ds = [int(d) for d in input().split()]
    q = int(input())
    queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
    print(*process_queries(ds, queries), sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
li = [0 for _ in range(10**6)]
for i in A:
    li[i] += 1
    ans += i


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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    cnts = {}
    for v in A:
        if not v in cnts:
            cnts[v] = 0
        cnts[v] += 1
    s = sum(A)
    for i in range(Q):
        b, c = B[i], C[i]
        if not b in cnts:
            cnt = 0
        else:
            cnt = cnts[b]
        s += (c - b) * cnt
        if not c in cnts:
            cnts[c] = 0
        cnts[c] += cnt
        cnts[b] = 0
        print(s)
    return

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:
def examA():
    S = SI()
    if S in alphabet:
        ans = "a"
    else:
        ans = "A"
    print(ans)
    return

def examB():
    N, K = LI()
    P = LI()
    P.sort()
    ans = sum(P[:K])
    print(ans)
    return

def examC():
    N = I()
    ans = ""
    while(N>0):
        N -= 1
        ans += alphabet[N%26]
        N //= 26
        if N==0:
            break
    print(ans[::-1])
    return

def examD():
    N = I()
    A = LI()
    D = defaultdict(int)
    for a in A:
        D[a] += 1
    S = sum(A)
    q = I()
    ans = [0]*q
    for i in range(q):
        a, b = LI()
        if not a in D:
            ans[i] = S
            continue
        S += (b-a)*D[a]
        D[b] += D[a]
        D[a] = 0
        ans[i] = S

    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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

ans = sum(A)

R = {}
for i in A:
  if i in R:
    R[i] += 1
  else:
    R[i] = 1

for b, c in BC:
  if b in R:
    t = R[b]
    R[b] = 0
    ans += t * (c - b)
    if c in R:
      R[c] += t
    else:
      R[c] = t
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
*A, = map(int, input().split())
Q = int(input())
s = sum(A)
c = Counter(A)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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


for b, c in Query:
    if b in dic:
        count = dic[b]
        if c in dic:
            dic[c] += count
        else:
            dic[c] = count
        del dic[b]
        ans += (c-b)*count
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))
C = Counter(A)
Q = int(input())
BC = [0]*Q
for i in range(Q):
    BC[i] = tuple(map(int,input().split()))

su = sum(A)
for b,c in BC:
    numb = C[b]
    C[b] = 0
    C[c] += numb
    su += (c - b) * numb
    print(su)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    d_a = Counter(a)
    q = int(input())
    answer = sum(a)
    for _ in range(q):
        b, c = map(int, input().split())
        if b in d_a:
            answer += (c - b) * d_a[b]
            if c in d_a:
                d_a[c] += d_a[b]
            else:
                d_a[c] = d_a[b]
            d_a[b] = 0
        print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
ans = sum(a)
q = int(input())
for _ in range(q):
	x, y = map(int, input().split())
	ans += (y-x) * c[x]
	print(ans)
	c[y] += c[x]
	c[x] = 0

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int, input().split()))
s = sum(arr)
m = {}
for e in arr:
    m[e] = m.get(e, 0)+1
for _ in range(int(input())):
    a, b = map(int, input().split())
    if a not in m:
        print(s)
        continue
    s += (b-a) * m[a]
    if b not in m:
        m[b] = 0
    m[b] += m[a]
    m[a] = 0
    print(s)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)

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

Q = int(input())

res = sum(A)

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

    print(res)

Submission status: Accepted

Solution code:
K = [0 for _ in range(10 ** 5 + 10)]
N = int(input())
A = list(map(int,input().rstrip().split(" ")))
ans = 0
for i in A:
    K[i] += 1
    ans += i
Q = int(input())
for i in range(Q):
    B,C = map(int,input().rstrip().split(" "))
    q = K[B]
    K[B] = 0
    K[C] += q
    ans += (C - B) * q
    print(ans)

Submission status: Accepted

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

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

    tot = sum(A)

    ctr = [0] * (10 ** 5 + 1)
    for x in A:
        ctr[x] += 1

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

        tot -= ctr[B] * B
        tot += ctr[B] * C

        ctr[C] += ctr[B]
        ctr[B] = 0

        ans.append(tot)

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


if __name__ == '__main__':
    main()

# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
q=int(input())
import collections
D=collections.defaultdict(int)
ans=sum(A)
for a in A:
  D[a]+=1
for _ in range(q):
  b,c=map(int,input().split())
  ans+=(c-b)*D[b]
  D[c]+=D[b]
  D[b]=0
  print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

S = sum(A)
Q = int(input())
ans = []
for i in range(Q):
    b, c = map(int, input().split())
    nb = d[b]
    diff = (c - b) * nb
    d[b] = 0
    d[c] += nb
    S += diff
    ans.append(S)

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

memo = {}
sum_ = 0
for i in range(n):
    if a[i] not in memo:
        memo[a[i]] = 0
    memo[a[i]] += 1
    sum_ += a[i]

for b, c in query:
    diff_num = 0
    if b not in memo:
        print(sum_)
        continue
    diff_cnt = memo[b]
    diff_num -= b * memo[b]
    memo[b] = 0
    
    if c not in memo:
        memo[c] = 0
    memo[c] += diff_cnt
    diff_num += c * diff_cnt
    sum_ += diff_num
    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())
C = [list(map(int,input().split())) for i in range(q)]

B = [0] * (10**5+2)

ans = sum(A)

for i in range(n):
    B[A[i]] += 1
for i in range(q):
    m = B[C[i][0]]
    B[C[i][0]] = 0
    B[C[i][1]] += m
    ans += m * (C[i][1]-C[i][0])
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
ans = sum(arr)
maxn = 10**5
maxn+=10
freq = [0 for i in range(maxn)]
for i in arr:
    freq[i]+=1
q = int(input())
for i in range(q):
    prev,nx = list(map(int,input().split()))
    p = freq[prev]
    if p==0:
        print(ans)
    else:
        ans-=(p*prev)
        ans+=(p*nx)
        freq[prev] = 0
        freq[nx]+=p
        print(ans)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
dic = collections.Counter(a)
total = sum(a)

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

Submission status: Accepted

Solution code:
N = int(input())
from collections import defaultdict as dd
a = list(map(int,input().split()))
Q = int(input())
bc = [tuple(map(int,input().split())) for _ in range(Q)]
dic=dd(int)
for val in a:
    dic[val] += 1
s = sum(a)
for b,c in bc:
    tmp = dic[b]
    dic[b] = 0
    dic[c] += tmp
    s += (c-b)*tmp
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
X = [0] * 100001
S = sum(A)
for a in A:
    X[a] += 1

for _ in range(int(input())):
    b, c = map(int, input().split())
    S += (c - b) * X[b]
    X[c] += X[b]
    X[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())
bc = [list(map(int, input().split())) for _ in range(q)]

counter = Counter(a)
sm = sum(a)
for b, c in bc:
    sm += counter[b] * (c - b)
    print(sm)
    counter[c] += counter[b]
    counter[b] = 0

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
input = stdin.buffer.readline
setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter
from itertools import combinations, permutations, combinations_with_replacement
from itertools import accumulate
from math import ceil, sqrt, pi, radians, sin, cos

MOD = 10 ** 9 + 7
INF = 10 ** 18

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
    
answer = sum(A)
for b, c in BC:
    answer += c * cnt[b] - b * cnt[b]
    cnt[c] += cnt[b]
    cnt[b] = 0
    print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

s = 0
d = defaultdict(int)
for i in range(n):
    s += a[i]
    d[a[i]] += 1

for b, c in query:
    nb = d[b]
    d[b] = 0
    d[c] += nb
    s += (c-b)*nb
    print(s)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N=int(input())
A=list(map(int,input().split()))
dic={}
for a in A:
    if a not in dic:
        dic[a]=0
    dic[a]+=1
S=sum(A)
Q=int(input())
for i in range(Q):
    b,c=map(int,input().split())
    if b in dic:
        val=dic[b]
        dic[b]=0
        if c not in dic:
            dic[c]=0
        dic[c]+=val
        S+=(c-b)*val
    #print("DEBUG")
    print(S)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
num = [0]*(10**5+1)
for i in a:
  num[i] += 1
sm = sum(a)
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  nx = num[x]
  sm = sm+y*nx-x*nx
  print(sm)
  num[x] = 0
  num[y] += nx

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
A = list(map(int, input().split()))
goukei = 0
jisho = defaultdict(int)
for i in range(n):
    goukei += A[i]
    jisho[A[i]] += 1

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter

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

cnt = Counter(A)
ret = sum(A)
for B, C in BC :
  ret = ret + cnt[B] * (C - B)
  cnt[C] += cnt[B]
  cnt[B] = 0
  print(ret)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import math
def II():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def MI():
	return map(int, sys.stdin.readline().split())

def SI():
	return sys.stdin.readline().strip()
n = II()
a = LI()
q = II()
d = [0]*(10**5+1)
s = 0
for i in a:
	d[i]+=1
	s+=i
for j in range(q):
	b,c = MI()
	s+=(c-b)*d[b]
	d[c]+=d[b]
	d[b] = 0
	print(s)

Submission status: Accepted

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

Submission status: Accepted

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

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

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


s=sum(a)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

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

s = sum(a)

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

Submission status: Accepted

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

    import collections
    count = collections.Counter(A)
    s = sum(A)

    Q = int(input())
    for _ in range(Q):
        B, C = [int(x) for x in input().split()]
        if B not in count:
            print(s)
            continue
        c = count[B]
        del count[B]
        count[C] = count.get(C, 0) + c
        s = s - B*c + C*c
        print(s)
 
 
if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10000)
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

count = Counter(A)
s = sum(A)
for b, c in BC:
    if b in count:
        s -= count[b] * b
        s += c * count[b]
        if c in count:
            count[c] += count[b]
        else:
            count[c] = count[b]
        count[b] = 0

    print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
f = [0] * 100001
s = sum(a)
for v in a:
    f[v] += 1

q = ni()
for z in range(q):
    b, c = na()
    s += (c-b) * f[b]
    f[c] += f[b]
    f[b] = 0
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
cnt = Counter(a)
s = sum(a)
q = int(input())
for _ in range(q):
    b, c = map(int, input().split())
    if b not in cnt.keys():
        print(s)
        continue
    t = cnt.pop(b)
    s -= b * t
    cnt[c] += t
    s += c * t
    print(s)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
from functools import lru_cache
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 998244353

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def main():
    N = int(input())
    A = read_list()
    Q = int(input())

    D = dict()
    for a in A:
        D[a] = D.setdefault(a, 0) + 1
    res = [""] * Q
    S = sum(A)
    for q in range(Q):
        B, C = read_values()
        S += (C - B) * D.setdefault(B, 0)
        D[C] = D.setdefault(C, 0) + D[B]
        D[B] = 0
        res[q] = str(S)
    print("\n".join(res))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
D = {}
for i in range(N):
    if A[i] in D:
        D[A[i]] += 1
    else:
        D[A[i]] = 1
Q = int(input())
S = sum(A)
for i in range(Q):
    B, C = map(int, input().split())
    diff = C - B
    cnt = 0
    if B in D:
        S += diff * D[B]
        print(S)
        if C in D:
            D[C] += D[B]
        else:
            D[C] = D[B]
        D[B] = 0
    else:
        print(S)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
total = 0
for i in a:
    d[i] += 1
    total += i
Q = int(input())

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

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter
from bisect import bisect_right, bisect_left

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = sum(A)
Q = int(input())
for i in range(Q):
    b, c = map(int, input().split())
    C[c] += C[b]
    ans -= b * C[b]
    ans += c * C[b]
    C[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    a = LI()
    q = I()
    m = 10**5+1
    f = [0]*m
    s = 0
    for i in a:
        s += i
        f[i] += 1
    for _ in range(q):
        b,c = LI()
        ns = s+(c-b)*f[b]
        f[c] += f[b]
        f[b] = 0
        print(ns)
        s = ns
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
As  = list(map(int, input().split()))
from collections import defaultdict
d = defaultdict(int)
for a in As:
    d[a] += 1
S = sum(As)

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