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:
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

from collections import Counter
C = Counter(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
D=dict()
for i in range(N):
    try:
        D[A[i]]+=1
    except:
        D[A[i]]=1

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

Q=int(input())
for _ in range(Q):
    b,c=map(int,input().split())
    if b in D:
        total=total-D[b]*b+D[b]*c
        print(total)
        try:
            D[c]+=D[b]
        except:
            D[c]=D[b]
        D[b]=0
    else:
        print(total)
        continue

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
a = list(map(int,readline().split()))
from collections import Counter
d = Counter(a)
s = sum(a)
q = int(readline())
for i in range(q):
  b,c = map(int,readline().split())
  m = d[b]
  s = s-m*(b-c)
  print(s)
  d.update({b:-m})
  d.update({c:m})

Submission status: Accepted

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

memo = defaultdict(int)
result = 0
for a in A:
    memo[a]+=1
    result += a

for _ in range(Q):
    bc = list(map(int, input().split()))
    b = bc[0]
    c = bc[1]
    tmp = memo[b]
    memo[c] += tmp
    memo[b] = 0
    result = result + c*tmp - b*tmp
    print(result)

Submission status: Accepted

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

from sys import stdin
input = stdin.readline

cnt = [0]*(10**5 + 1)
total = 0
for i in range(n):
  cnt[A[i]] += 1
  total += A[i]
  
for i in range(q):
  b,c = map(int, input().split())
  cnt[c] += cnt[b]
  total -= cnt[b]*b
  total += cnt[b]*c
  cnt[b] = 0
  print(total)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
ans=sum(A)
x=[0 for i in range(10**5)]
for i in range(N):
  x[A[i]-1]+=1
#print(x)
for i in range(Q):
  b,c=map(int,input().split())
  j=x[b-1]
  x[c-1]+=x[b-1]
  x[b-1]=0
  ans+=c*j-b*j
  print(ans)
  #print(x)

Submission status: Accepted

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

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

Q =  int(input())

SUM = sum(A)
#print(lst[:10])

for i in range(Q):
  b, c = map(int, input().split())
  # b の個数
  cnt_b = lst[b]
  SUM += cnt_b * (c  - b)
  print(SUM)
  lst[c] += cnt_b
  lst[b] =  0

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

ans=sum(A)
Q=int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
A = {}
B = list(map(int,input().split()))
S = sum(B)
for i in B:
    if i in A:
        A[i] += 1
    else:
        A[i] = 1
#print(A)
q = int(input())
for _ in range(q):
    b,c = map(int,input().split())
    if (b in A) and A[b] > 0:
        S += (c-b)*A[b]
        if not c in A:
            A[c] = 0
        A[c] += A[b]
        A[b] = 0
    print(S)

Submission status: Accepted

Solution code:
from collections import Counter
import sys

def input():
    return sys.stdin.readline().strip()

def main():

    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:
        tmp = a[b]
        a[b] = 0
        ans -= b * tmp
        a[c] += tmp
        ans += c * tmp
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
A=list(map(int,input().split()))
d=defaultdict(int)
for a in A:
    d[a]+=1
ans=sum(A)
Q=int(input())
for _ in range(Q):
    b,c=map(int,input().split())
    ans+=c*d[b]-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 = list(map(int,input().split()))
q = int(input())
d = defaultdict(lambda: 0)
ans = sum(a_list)
for i in a_list:
    d[i] += 1
    
ans = sum(a_list)
for i in range(q):
    a,b = map(int,input().split())
    ans = ans + b*d[a] - a*d[a]
    d[b] += d[a]
    d[a] -= d[a]
    print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import numpy as np
import collections


def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    cc = collections.Counter(A)
    ans = sum(A)
    for i in range(1,Q+1):
        cb = cc[B[i-1]]
        cc[B[i-1]] = 0
        cc[C[i-1]] += cb
        ans -= cb * B[i-1]
        ans += cb * C[i-1]
        print(ans)

    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:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
BC=[list(map(int,input().split())) for i in range(Q)]
from collections import Counter
x=Counter(A)
s=sum([k*v for k,v in x.items()])
for b,c in BC:
    if b in x:
        s+=(c-b)*x[b]
        if c in x:
            x[c]+=x[b]
        else:
            x[c]=x[b]
        del x[b]
    print(s)

Submission status: Accepted

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

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

q = int(input())
ans = sum(a)

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

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
mp = dict()
ans = 0
for i in range(n):
    try:
        mp[a[i]]+=1
    except:
        mp[a[i]]=1
    ans += a[i]


q= int(input())
while q:
    q-=1
    b,c = map(int, input().split())
    try:
        cnt = mp[b]
        try:
            mp[c]+=cnt
        except:
            mp[c]=cnt
        mp[b]=0
        ans += cnt*(c-b)
    except:
        pass
    print(ans)

Submission status: Accepted

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

ct = Counter(As)
S = sum(As)

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
total = sum(A)
from collections import defaultdict
d = defaultdict(lambda: 0)
for a in A:
    d[a] += 1
Q = int(input())
ans = []
for i in range(Q):
    x,y = map(int, input().split())
    total += y*d[x]-x*d[x]
    d[y] += d[x]
    d[x] = 0
    ans.append(total)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import Counter

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

asum=sum(A)

C=Counter(A)

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

    asum=asum+(c-b)*C[b]

    C[c]=C[c]+C[b] if c in C else C[b]
    C[b]=0

    print(asum)

Submission status: Accepted

Solution code:
import collections
dic = collections.defaultdict(int)
n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
sm = 0
for i in range(n):
    dic[a[i]] += 1
    sm += a[i]
queries = []
for i in range(q):
    queries.append([int(j) for j in input().split()])

for i in range(q):
    b = queries[i][0]
    c = queries[i][1]
    sm += dic[b] * (c-b)
    dic[c] += dic[b]
    dic[b] = 0
    print(sm)

Submission status: Accepted

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

co = collections.Counter(a)

s = [0]*(q+1)
s[0] = sum(a)

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

Submission status: Accepted

Solution code:
#D
from collections import Counter
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[0]*Q
C=[0]*Q
for i in range(Q):
    B[i],C[i] = map(int,input().split())
    
d=dict(Counter(A))
#print(d)
summ=sum(A)

for i in range(Q):
    if C[i] not in d:
        d[C[i]]=0
    if B[i] in d:
        summ -= d[B[i]]*B[i]
        summ += d[B[i]]*C[i]
        d[C[i]] += d[B[i]]
        d[B[i]]=0
    print(summ)
        
#print(d)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
b, c = [], []
smap = {}
sum_ = sum(a)

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

for aa in a:
    smap[aa] = smap.get(aa, 0) + 1

# print(smap)

for i in range(q):

    try:
        count = smap[b[i]]
        diff = (c[i] - b[i]) * count
        smap[c[i]] = smap.get(c[i], 0) + count
        del smap[b[i]]
        sum_ += diff
        # print(diff)
    except KeyError:
        pass

    print(sum_)
    # print(smap)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

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

# print(c)
tmpsum = sum(a)

q = int(input())

for i in range(q):
    ans = tmpsum
    before, after = map(int, input().split())

    num_of_before = c[before]
    # print(c[before])

    ans += num_of_before * (after - before)
    tmpsum = ans

    c[after] += num_of_before
    c[before] = 0
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict

N = int(input())

arr = np.array(list(map(int, input().split())))
unique, cnts = np.unique(arr, return_counts=True)

counts = defaultdict(int)
sum = arr.sum()

for key, val in zip(unique, cnts):
    counts[key] = val

Q = int(input())

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
# from collections import defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    Q = int( input())
    BC = [ tuple( map( int, input().split())) for _ in range(Q)]
    L = [0]*(10**5+1)
    ans = sum(A)
    for a in A:
        L[a] += 1
    ANS = []
    for b, c in BC:
        ans = ans + L[b]*c - L[b]*b
        L[c] += L[b]
        L[b] = 0
        ANS.append(ans)

    print("\n".join( map( str, ANS)))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

from collections import Counter
counter = Counter(A)

for q in range(Q):
  b, c = map(int, input().split())
  b_count = counter.get(b, 0)
  counter[c] = counter.get(c, 0) + b_count
  if b_count:
    del counter[b]
  b_sum = b * b_count
  c_sum = c * b_count
  a_sum = a_sum - b_sum + c_sum
  print(a_sum)

Submission status: Accepted

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

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()))
ac = Counter(A)

a_sum = sum(A)
Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())

    if b in ac:
        a_sum += (c-b)*ac[b]
        ac[c] += ac[b]
        del ac[b]
    print(a_sum)

Submission status: Accepted

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

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

answer = []
for _ in range(q):
    b, c = map(int, input().split())
    if b in dic:
        if c in dic:
            dic[c] = dic[b] + dic[c]
        else:
            dic[c] = dic[b]
        ans += (c - b) * dic.pop(b)
    answer.append(ans)

for i in answer:
    print(i)

Submission status: Accepted

Solution code:
from collections import Counter
def main():
    N=int(input())
    A=list(map(int,input().split()))
    Q=int(input())
    count= Counter(A)
    ans=sum(A)
    for i in range(Q):
        b,c=map(int,input().split())
        if b in count.keys():
            if c in count.keys():
                count[c] = count[b]+count[c]
            else:
                count[c] = count[b]
            ch=count.pop(b)
            ans+=((c-b)*ch)
            print(ans)
        else:
            print(ans)
main()

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()
q = ni()
from collections import Counter

d = Counter(a)
s = sum(a)

for i in range(q):
    b,c = na()
    k = d[b]
    s += k*(c-b)
    d[c]+=d[b]
    d[b] = 0
    print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
q = int(input())
cnt = defaultdict(int)
for x in a:
    cnt[x] += 1
ans = [0] * q
total = sum(a)
for i in range(q):
    b, c = map(int, input().split())

    cnt[c] += cnt[b]
    total = total - b * cnt[b] + (cnt[b]) * c
    cnt[b] = 0
    ans[i] = total

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int,input().split()))
q = int(input())
count_map = Counter(a)
res = sum(a)
ans = []
for _ in range(q):
    b, c = map(int, input().split())
    if b not in count_map or count_map[b] == 0:
        ans.append(res)
    else:
        diff = (c-b)*count_map[b]
        count_map[c] += count_map[b]
        count_map[b] = 0
        res += diff
        ans.append(res)
print(*ans, sep='\n')

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
sumA = sum(A)
counter = Counter(A)
Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    sumA += (counter[B]*C-counter[B]*B)
    counter[C] += counter[B]
    counter[B] = 0
    print(sumA)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = [0] * 100010
ans = 0
for i in range(n):
    num[a[i]] += 1
    ans += a[i]

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

n = int(input())
alst = list(map(int, input().split()))
q = int(input())
dd = defaultdict(int)
for num in alst:
    dd[num] += 1
ans = sum(alst)
for _ in range(q):
    b, c = map(int, input().split())
    ans -= b * dd[b]
    ans += c * dd[b]
    dd[c] += dd[b]
    dd[b] = 0
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
C = Counter(A)
total = sum(A)
for s in sys.stdin.readlines():
    b, c = map(int, s.split())
    k = C[b]
    total += (c - b) * k
    print(total)
    C[b] = 0
    C[c] += k

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

num_list = [0 for _ in range(100001)]

all_val = 0
for i in range(N):
    all_val += A[i]
    num_list[A[i]] += 1

for i in range(Q):
    before = bc[i][0]
    after = bc[i][1]
    
    all_val += (after-before) * num_list[before]
    num_list[after] += num_list[before]
    num_list[before] = 0
    
    print(all_val)

Submission status: Accepted

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

Submission status: Accepted

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

table = {}
s = 0
for num in a:
    if num not in table:
        table[num] = 1
    else:
        table[num] += 1
    s += num

for i in range(q):
    frm, to = b[i], c[i]
    if frm in table:
        s += (to - frm) * table[frm]
        if to not in table:
            table[to] = table[frm]
        else:
            table[to] += table[frm]
        table.pop(frm)
    print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ma = [0] * (100000 + 1)

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

Q = int(input())

s = sum(A)

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
read = sys.stdin.read
readline = sys.stdin.readline

_ = int(readline())
alst = list(map(int, readline().split()))
_ = int(readline())
m = map(int, read().split())
bc = list(zip(m, m))
s = sum(alst)
dic = defaultdict(int)
for i in alst:
  dic[i] += 1

for b, c in bc:
  pred = dic[b]
  dic[c] += pred
  dic[b] = 0
  s += (c - b) * pred
  print(s)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))
mydict = {}
total = 0
for a in A:
    mydict[a] = mydict[a] + 1 if a in mydict else 1
    total += a

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

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
total = sum(a)
cnt = [0] * (10 ** 5 + 1)  # cnt[i] i が現在何個あるか
for i in a:
    cnt[i] += 1
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    total += (c - b) * cnt[b]
    print(total)
    cnt[c] += cnt[b]
    cnt[b] = 0

Submission status: Accepted

Solution code:
from collections import Counter

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

S = sum(A)
cnt = Counter(A) # Listなど
ans = [0] * Q
for i in range(Q):
    B, C = [int(x) for x in input().split()]
    S += (C - B) * cnt[B]
    cnt[C] += cnt[B]
    cnt[B] = 0
    ans[i] = S

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

Submission status: Accepted

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

N = int(input())
*A, = map(int, input().split())
C = Counter(A)
S = sum(A)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce, lru_cache  # @lru_cache(None)
from fractions import gcd
import sys  # def input(): return sys.stdin.readline().rstrip() # sys.setrecursionlimit(10**6)

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

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

ans = sum(key*value for key, value in d.items())
for b, c in BC:
    db = d[b]
    dc = d[c]
    d[b] = 0
    d[c] = dc + db
    ans += c*(dc+db) - (b*db + c*dc)
    print(ans)

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    D = [0] * (1 + 10 ** 5)
    sA = sum(A)
    for a in A: D[a] += 1
    Q = int(input())
    Ans = [-1] * Q
    for i in range(Q):
        B, C = map(int, input().split())
        sA += (C - B) * D[B]
        D[C] += D[B]
        D[B] = 0
        Ans[i] = sA
    print(*Ans, sep="\n")

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    num = [0] * 100005
    A = list(map(int,input().split()))
    S = sum(A)
    for a in A:
        num[a] += 1
    
    Q = int(input())
    for _ in range(Q):
        c,d = map(int,input().split())
        x = num[c]
        num[c] = 0
        S -= x * c
        num[d] += x
        S += x * d
        #print(num[:10])
        print(S)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

ans = sum(a)
cnter = collections.Counter(a)

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

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
q = int(input())
#b = [list(map(int, input().split())) for _ in range(q)]
c = collections.Counter(a)
ans = sum(a)

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

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from scipy.sparse.csgraph import floyd_warshall
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations, combinations_with_replacement
from heapq import heappop, heappush, heapify
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    n = inp()
    a = inpl()
    dic = defaultdict(int)
    ans = sum(a)
    for i in range(n):
        dic[a[i]] += 1
    q = inp()
    for _ in range(q):
        b,c = inpm()
        ans += dic[b]*(c-b)
        dic[c] += dic[b]
        dic[b] = 0
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# D - Replacing
NUM = 10**5
N = int(input())
A = list(map(int,input().split()))
S = [0]*(NUM+1)
ans = 0
for x in A:
    S[x] += 1
    ans += x
Q = int(input())
for _ in range(Q):
    B,C = map(int,input().split())
    ans += (C-B)*S[B]
    print(ans)
    S[C] += S[B]
    S[B] = 0

Submission status: Accepted

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

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

ans = sum(a)
q = int(input())

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

Submission status: Accepted

Solution code:
import copy
n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*10**5

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

ans=sum(a)

for i in range(q):
    b,c=map(int,input().split())
    temp=copy.deepcopy(l[b-1])
    ans-=temp*(b-c)
    #print(l)
    print(ans)
    l[b-1]=0
    l[c-1]+=temp

Submission status: Accepted

Solution code:
import numpy as np

n = int(input())

a = list(map(int, input().split()))
l = [0 for i in range(100010)]

q = int(input())

s = np.sum(a)

for ae in a:
    l[ae] += 1

ans = []

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

    m_num = l[b]
    l[b] = 0
    m_s = m_num*b

    p_s = m_num*c
    l[c] += m_num

    s = s - m_s + p_s

    ans.append(s)

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

Submission status: Accepted

Solution code:
n = int(input())
temp = [int(_) for _ in input().split(' ')]
a = [0 for _ in range(100001)]
for k in temp:
    a[k] += 1
s = sum([i * a[i] for i in range(100001)])

q = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
aa = list(map(int, input().split()))
total = sum(aa)

q = int(input())
from collections import Counter
dic = Counter(aa)
for i in range(q):
    b, c = map(int, input().split())
    nb = dic.pop(b,0)
    total += nb * (c-b)
    print(total)
    dic[c] = dic.get(c,0) + nb

Submission status: Accepted

Solution code:
import collections

n = int(input())
l = list(map(int, input().split()))
c = collections.Counter(l)
s = sum(l)

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

Submission status: Accepted

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

Cnt = collections.Counter(A)
S = sum(A)

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

Submission status: Accepted

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

MAXX = 10**5 + 5
count = [0]*MAXX

sumz = sum(num)
for n in num:
    count[n] += 1

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

    print(sumz)

Submission status: Accepted

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

my_dict = dict()

current_sum = sum(a)

for item in a:
    if item in my_dict:
        my_dict[item] += 1
    else:
        my_dict[item] = 1

for item in bc:
    b, c = item
    if c in my_dict:
        if b in my_dict:
            cnt = my_dict.pop(b)
            my_dict[c] += cnt
            current_sum += (c - b) * cnt
    else:
        if b in my_dict:
            my_dict[c] = my_dict.pop(b)
            current_sum += (c - b) * my_dict[c]
    print(current_sum)