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())
tmpDic = {}
res = sum(A)

for i in range(N):
    if A[i] in tmpDic:
        tmpDic[A[i]] += 1
    else:
        tmpDic[A[i]] = 1

for i in range(Q):
    B, C= list(map(int, input().split()))
    if B in tmpDic and tmpDic[B] > 0:
        tmp = tmpDic[B]
        tmpDic[B] = 0
        res += (C - B)* tmp
        
        if C in tmpDic:
            tmpDic[C] += tmp
        else:
            tmpDic[C] = tmp
    print(res)

Submission status: Accepted

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

rep = dict()
for i in range(N):
    if A[i] in rep:
        rep[A[i]] += 1
    else:
        rep[A[i]] = 1

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

Submission status: Accepted

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

def main():
    from collections import Counter

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

    ans = [None] * Q
    Asum = sum(A)
    A_Counter = Counter(A)
    for q in range(Q):
        B, C = map(int, input().split())
        Asum = Asum + (C-B)*A_Counter[B]
        A_Counter[C] += A_Counter[B]
        A_Counter[B] = 0

        ans[q] = Asum

    print('\n'.join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,a,d = int(input()),list(map(int,input().split())),[0 for i in range(100100)]
for x in a:
	d[x] += 1
s,q = sum(a),int(input())
for i in range(q):
	b,c = map(int,input().split())
	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()))
q = int(input())
num_list = [0 for i in range(100001)]
for i in a:
    num_list[i] += 1
ans = sum(a)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
a= list(map(int, input().split()))
q=int(input())
b= [list(map(int, input().split())) for i in range(q)]
d=defaultdict(int)
ans=sum(a)

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

for i,j in b:
    ans+=d[i]*(j-i)
    print(ans)
    d[j]+=d[i]
    d[i]=0

Submission status: Accepted

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

sum_ans = sum(a_list)

count_list = [0] * 100001
for i in range(n):
    count_list[a_list[i]] += 1

for j in range(len(b_c_list)):
    from_j = b_c_list[j][0]
    to_j = b_c_list[j][1]
    # 和を求める
    sum_diff = (to_j - from_j) * count_list[from_j]
    sum_ans += sum_diff
    print(sum_ans)
    # 変換
    count_list[to_j] += count_list[from_j]
    count_list[from_j] = 0

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

if __name__ == "__main__":
    n = int(input())
    a = list(map(int,input().split()))
    q = int(input())
    cnt = [0]*(10**5+7)
    for i in range(n):
        cnt[a[i]]+=1
    ruiseki = sum(a)
    for i in range(q):
        b,c = map(int,input().split())
        d = cnt[b]
        e = d*(c-b)
        cnt[c] += d
        cnt[b] -= d
        ruiseki += e
        print(ruiseki)

Submission status: Accepted

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

import sys
import numpy as np
from collections import defaultdict
int1 = lambda x: int(x) - 1
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

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

Q = int(readline())
m = map(int, read().split())
B, C = zip(*zip(m, m))

dicts = defaultdict(int)
s = 0
for a in A:
    dicts[a] += 1
    s += a

for b, c in zip(B, C):
    cnt = dicts[b]
    dicts[b] = 0
    dicts[c] += cnt
    s += cnt * (c - b)
    print(s)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def resolve():
    from collections import defaultdict
    N = int(input())
    A = [int(i) for i in input().split()]
    d = defaultdict(int)
    sumA = 0
    for a in A:
        d[a] += 1
        sumA += a
    Q = int(input())
    BBCC = [list(map(int, input().split())) for _ in range(Q)]
    for b, c in BBCC:
        sumA = sumA + (d[b] * c - d[b] * b)
        tmp = d[b]
        d[c] += tmp
        d[b] = 0
        print(sumA)


resolve()

Submission status: Accepted

Solution code:
import numpy as np

N=int(input())
A=list(map(int,input().split()))
Adic={}
for i in A:
  if Adic.get(i)==None:
    Adic[i]=1
  else:
    Adic[i]+=1
Q=int(input())
ope=[]

for i in range(Q):
  ope.append(list(map(int,input().split())))

A=np.array(A)

sum=0
for key,value in Adic.items():
  sum+=key*value
for b,c in ope:
  if Adic.get(b)!=None:
    if Adic.get(c)==None:Adic[c]=0
    sum=sum-b*Adic[b]+c*Adic[b]
    Adic[c]+=Adic.pop(b)
    print(sum)
  else:
    print(sum)

Submission status: Accepted

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

m = {}
for i in a:
    if i in m.keys():
        m[i] = m[i] + 1
    else:
        m[i] = 1

ans = 0
for k in m:
    ans += m[k] * k

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

Solution code:
from collections import Counter

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

cnt = Counter(a)

ans = []
sum_ = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    bv, cv = cnt[b], cnt[c]
    sum_ += c*(cv+bv) - b*bv - c*cv
    cnt[c] += bv
    cnt[b] = 0
    ans.append(sum_)

print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(input().split())
q = int(input())
ansList = [0]*q
d = Counter(A)
Sum = sum(map(int,A))

for i in range(q):
    b,c = input().split()
    Sum = Sum - int(b)*d[b] + int(c)*d[b]
    if b in d:
        if c in d:
            d[c] += d.pop(b)
        else:
            d[c] = d.pop(b)
    ansList[i]  +=  Sum

[print(ans) for ans in ansList]

Submission status: Accepted

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

q = int(input())
b,c = [],[]

for i in range(q):
    bi,ci = map(int,input().split())
    b.append(bi),c.append(ci)
for i in range(q):
    bi,ci = b[i],c[i]
    x -= bi*count[bi]
    x += ci*count[bi]
    count[ci]+=count[bi]
    count[bi] = 0
    print(x)

Submission status: Accepted

Solution code:
N=int(input())

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

Amap=dict()

for i in range(N):
    if A[i] in Amap:
        Amap[A[i]]+=1
    else:
        Amap[A[i]]=1

# print(Amap)

s = 0
for k in Amap.keys():
    s += (int(k)*Amap[k])


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

    if B in Amap:
        if C in Amap:
            Amap[C] += Amap[B]
            s += (C-B)*Amap[B] 
        else:
            Amap[C] = Amap[B]
            s += (C-B)*Amap[B] 

    else:
        if C in Amap:
            Amap[C] += 0
        else:
            Amap[C] = 0

    Amap[B] = 0
    # print(i, B, C, Amap)


    ans.append(s)
    # print(s)

for s in ans:
    print(s)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_dict = {}
sum = 0
for i in range(n):
    if a[i] not in a_dict:
        a_dict[a[i]] = 0
    a_dict[a[i]] += 1
    sum += a[i]
q = int(input())
for i in range(q):
    b,c = map(int, input().split())
    # bがcになったときに増加する数を数えれば良い
    # b*bの数を引いて c*cの数を足せば良い
    if b in a_dict:
        tmp = a_dict[b]
        a_dict[b] = 0
        if c not in a_dict:
            a_dict[c] = 0
        a_dict[c] += tmp
        sum = sum + tmp * c - tmp * b

    #ans = 0
    #for key,value in a_dict.items():
    #    ans += key*value
    print(sum)

Submission status: Accepted

Solution code:
from collections import Counter
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(100000)


def main():
    N = int(input().strip())
    A_list = [int(i) for i in input().strip().split()]
    Q = int(input().strip())
    _sum = sum(A_list)
    num_count = Counter(A_list)
    for _ in range(Q):
        B, C = [int(i) for i in input().strip().split()]
        if B in num_count:
            if C in num_count:
                num_count[C] = num_count[C] + num_count[B]
            else:
                num_count[C] = num_count[B]

            _sum = _sum - (num_count[B] * B) + num_count[B] * C
            del num_count[B]
            print(_sum)
        else:
            print(_sum)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
d = {}
total = 0
for i in a:
  total += i
  d[i] = d.get(i, 0) + 1

#クエリによって、それぞれの数値の個数を変更し、
#対象となる個数×差分で合計を修正し出力する

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
q=int(input())
l=[0]*q
ans=sum(a)
for i in range(q):
    b,c=map(int,input().split())
    l[i]=(b,c)
book={}
for i in a:
    if i in book:
        book[i]+=1
    else:
        book[i]=1

for i in range(q):
    if l[i][0] in book:
        if l[i][1] in book:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]+=book[l[i][0]]
            book[l[i][0]]=0
        else:
            ans+=(l[i][1]-l[i][0])*book[l[i][0]]
            book[l[i][1]]=book[l[i][0]]
            book[l[i][0]]=0
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
numlist = list(map(int,input().split()))
numcount = [0]*10**6

numset = set()
for num in numlist:
    numcount[num] += 1
    numset.add(num)
n = int(input())
anslist = []
result = 0
for num in list(numset):
    result += numcount[num]*num
    
for i in range(n):
    b,c = map(int,input().split())
    numcount[c] += numcount[b]
    result += (c-b)*numcount[b]
    anslist.append(result)

    numcount[b] = 0
    numset.add(c)
    numset.discard(b)

for ans in anslist:
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import math
import collections
import bisect
import itertools
from collections import Counter


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

    counter = Counter(A)
    sumA = sum(A)
    # print(counter)
    for i in range(Q):
        b, c = map(int, input().split())
        if b in counter:
            if c in counter:
                counter[c] = counter[c] + counter[b]
            else:
                counter[c] = counter[b]
            sumA += (c - b) * (counter[b])
            del counter[b]
        print(sumA)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
COL = collections.Counter(A)
ret = 0
ans = list()
for c in COL.keys():
    ret += COL[c] * c
for i in range(Q):
    B,C = map(int,input().split())
    if B in COL.keys():
        if C in COL.keys():
            COL[C] += COL[B]
            
            ret += (C-B) * COL[B]           
        else:
            COL[C] = COL[B]
            ret += (C-B) * COL[B]
        COL.pop(B)
    ans.append(ret)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
# ABC171 D 

import itertools

n = int(input())
a_l = [int(x) for x in input().split()]
q = int(input())

a_l.sort()
gr = itertools.groupby(a_l)
a_d = dict()
a_sum = sum(a_l)
for key, group in gr:
    a_d[key] = len(list(group))
for i in range(q):
    _b, _c = map(int, input().split())
    try:
        _b_num = a_d.pop(_b)
        a_sum = a_sum + (_c - _b) * _b_num
        try:
            _c_num = a_d[_c]
            a_d[_c] = _b_num + _c_num
        except:
            a_d[_c] = _b_num
    except:
        pass
    print(a_sum)

Submission status: Accepted

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

import collections

result = sum(a)
counter = collections.Counter(a)

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

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    q=int(input())
    bcList=[]
    for _ in range(q):
        bcList.append(list(map(int,input().split())))
    return n,a,q,bcList

def main(n,a,q,bcList):
    hist=[0]*(10**5+1)
    for v in a:
        hist[v]+=1

    sum=0
    for i in range(1,10**5+1):
        sum+=i*hist[i]

    for b,c in bcList:
        sum=sum+hist[b]*(c-b)
        hist[c]+=hist[b]
        hist[b]=0
        print(sum)


if __name__=='__main__':
    n,a,q,bcList=readinput()
    main(n,a,q,bcList)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
val2ind = Counter(list(map(int, input().split())))
ans = sum([key*val2ind[key] for key in val2ind])
Q = int(input())

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

Submission status: Accepted

Solution code:
def main():
    nmax = 100000
    n = int(input())
    values = [0] * nmax
    a = [int(v) for v in input().split()]
    for v in a:
        values[v-1] += 1
    asum = sum(a)

    q = int(input())
    for _ in range(q):
        b, c = [int(v) for v in input().split()]
        asum += values[b-1] * (c - b)
        values[c-1] += values[b-1]
        values[b-1] = 0
        print(asum)

main()

Submission status: Accepted

Solution code:
import collections

num = int(input())
original = list(map(int, input().split()))
trial_num = int(input())

total = sum(original)
# now_list = original
count_dict = collections.Counter(original)

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

Submission status: Accepted

Solution code:
import math
# from collections import Counter

# N = int(input()) # 1行, 単数
# arg = list(map(int, input().split())) # 1行, 配列
# D = Counter(arg) # 出現数カウント

# print('Yes')
# print('No')
# print()
import collections
N = int(input()) # 1行, 単数
A = list(map(int, input().split())) # 1行, 配列
Q = int(input()) # 1行, 単数
counter = collections.Counter(A)
ans = 0
for i in counter.keys():
  ans = ans + i * counter[i]

while True:
  try:

    B,C = list(map(int, input().split())) # 1行, 配列
    old = C * counter[C] + counter[B] * B
    counter[C] = counter[C] + counter[B]
    del counter[B]
    new = C * counter[C]
    ans = ans + (new - old)
    print(ans)
  except:
    break;

Submission status: Accepted

Solution code:
n = int(input())
a_count_list = [0 for i in range(10**5+1)]
for i in input().split(" "):
    x = int(i)
    a_count_list[x-1]+=1
total = sum([(i+1)*x for i,x in enumerate(a_count_list)])

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from sys import stdin
#, setrecursionlimit, stdout
#setrecursionlimit(1000000)
#from collections import deque
#from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin
def ii(): return int(stdin.readline())
def fi(): return float(stdin.readline())
def mi(): return map(int, stdin.readline().split())
def fmi(): return map(float, stdin.readline().split())
def li(): return list(mi())
def si(): return stdin.readline().rstrip()
def lsi(): return list(si())
#mod=1000000007
res=['Yes', 'No']
############# CODE STARTS HERE #############


test_case=1
while test_case:
    test_case-=1


    cnt=[0]*100005
    n=ii()
    a=li()
    for i in a:
        cnt[i]+=1
    s=sum(a)
    for _ in range(ii()):
        x, y=mi()
        s+=(y-x)*cnt[x]
        print(s)
        cnt[y]+=cnt[x]
        cnt[x]=0

Submission status: Accepted

Solution code:
import collections
def my_index_multi(l, x):
    return [i for i, _x in enumerate(l) if _x == x]
N=int(input())
A=list(map(int,input().split()))
goukei=sum(A)
Q=int(input())
BC=[]
for i in range(Q):
    BC.append(list(map(int,input().split())))
c = collections.Counter(A)
for i in BC:
    goukei+=c[i[0]]*(i[1]-i[0])
    c[i[1]]=c[i[0]]+c[i[1]]
    c[i[0]]=0
    print(goukei)

Submission status: Accepted

Solution code:
import collections
N = int(input())
a = list(map(int, input().split()))
a_c = collections.Counter(a)
Q = int(input())
BC = [list(map(int, input().split())) for _ in range(Q)]
s_old = 0
for k, v in a_c.items():
    s_old += k*v
for bc in BC:
  b = bc[0]
  c = bc[1]
  s = s_old
  if b in a_c:
    n = a_c.pop(b)
    a_c[c]+=n
    s-=n*b
    s+=n*c
  print(s)
  s_old = s

Submission status: Accepted

Solution code:
n = int(input().strip()) 
a = [int(x.strip()) for x in input().strip().split(' ')]

x = {}
sum = 0
for i in a:
  x[i] = (x[i] if i in x else 0) + 1
  sum = sum + i

q = int(input().strip())
for i in range(0, q):
  b, c = [int(x.strip()) for x in input().strip().split(' ')]
  if b in x and b != c:
    sum = sum + (c - b) * x[b]
    if c in x:
      x[c] = x[c] + x[b]
    else:
      x[c] = x[b]
    del x[b]    
  print(sum)

Submission status: Accepted

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

Submission status: Accepted

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

import collections
cnt = collections.Counter(a)
ans = 0
for ai, ni in cnt.items():
    ans += ai * ni
for _ in range(q):
    bi, ci = map(int, input().split())
    tmp = cnt[bi]
    del cnt[bi]
    cnt[ci] = tmp + cnt[ci]
    ans = ans - bi * tmp + ci * tmp
    print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n=int(input())
A=list(map(int,input().split()))
k={}
ans=sum(A)
for i in A:
  if i in k:
    k[i]+=1
  else:
    k[i]=1
q=int(input())
for i in range(q):
  b,c=map(int,input().split())
  if b in k:
    f=c*k[b]-b*k[b]
    ans+=f
    p=k[b]
    del k[b]
    if c in k:
      k[c]+=p
    else:
      k[c]=p
  print(ans)

Submission status: Accepted

Solution code:
import sys, math

def calcSum(AList, B, C, Sum):
    Len = AList[B]
    if(Len == 0):
        return Sum
    Sum += (C-B) * Len

    AList[B] = 0
    AList[C] += Len
    return Sum

if(__name__ == "__main__"):
    N= int( input().strip() )

    Max = int(10**5)+1
    AList = [0] * Max
    A_str = input().strip().split()
    N_Queries = int( input().strip() )

    sum = 0
    for i in range(N):
        value = int(A_str[i])
        AList[value] += 1
        sum += value
    BCs = []
    Sums = [sum]
    for i in range(N_Queries):
        BC_str =  input().strip().split()
        B = int(BC_str[0])
        C = int(BC_str[1])
        Sums.append( calcSum(AList, B, C, Sums[-1]) )
        """
        BC = [ int(BC_str[0]), int(BC_str[1]) ]
        BCs.append(BC)
        """

    for i in range(1, 1+N_Queries):
        print(Sums[i])

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
q = int(input())
sm = sum(a)
dic = dict(Counter(a))
for _ in range(q):
    b,c = map(int,input().split())
    if b not in dic:
        print(sm)
    else:
        dif = c-b
        sm = sm+dic[b]*dif
        print(sm)
        x = dic[b]
        if c in dic:
            dic[c]+=x
        else:
            dic[c]=x
        dic[b]=0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int( input() )
a_array = list( map( int, input().split() ) )
q = int( input() )
bc_array = []
for _ in range( q ):
    bc_i = list( map( int, input().split() ) )
    bc_array.append( bc_i )

a_list = [ 0 for _ in range( 10 ** 5 + 1 ) ]
for a in a_array:
    a_list[ a ] += 1

s = 0
for i in range( 10 ** 5 + 1 ):
    s += i * a_list[ i ]

for b, c in bc_array:
    s = s + ( c - b ) * a_list[ b ]
    a_list[ c ] += a_list[ b ]
    a_list[ b ] = 0
    print( s )

Submission status: Accepted

Solution code:
n = int(input())
data = list(map(int, input().split()))
q = int(input())
d = {}
big = 10**5+100

for i in range(big):
  d[i+1] = []
for i in data:
  d[i].append(i)

ans = sum(data)
for i in range(q):
  a, b = map(int, input().split())
  #print(len(d[a]))
  ans += len(d[a]) * (b-a)
  d[b] = d[b] + d[a]
  d[a] = []
  print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
A = list(map(int, input().split()))
counter = Counter(A)
value = sum(A)

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

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
Q=int(input())
B=[]
C=[]
for i in range(Q):
  Bt,Ct=map(int,input().split())
  B+=[Bt]
  C+=[Ct]
num =[0 for i in range(10**5+3)]
for i in range(N):
  num[A[i]]+=1
S=0
for i in range(10**5+1):
  S+=num[i]*i
for i in range(Q):
  tmp=num[B[i]]
  num[B[i]] =0
  num[C[i]] += tmp
  S=S+tmp*(C[i]-B[i])
  print(S)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
import string
def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = [list(map(int, input().split())) for i in range(q)]
    b = [bc[i][0] for i in range(q)]
    c = [bc[i][1] for i in range(q)]
    dic = Counter(a)
    base = sum(a)
    for i in range(q):
        celb = deepcopy(dic[b[i]])
        celc = deepcopy(dic[c[i]])
        dic[c[i]] += dic[b[i]]
        dic[b[i]] = 0
        base += (c[i]-b[i])*(celb)
        print(base)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

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

Submission status: Accepted

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

s=sum(a)

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

Submission status: Accepted

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

cnt = [0] * (100000+1)
ans = 0
for i in range(N):
  cnt[A[i]] += 1
  ans += A[i]
#
Q = int(input())
for i in range(Q):
  B, C = map(int, input().split())
  ans += (C-B) * cnt[B]
  cnt[C] += cnt[B]
  cnt[B] = 0
  print(ans)
#

Submission status: Accepted

Solution code:
from collections import defaultdict

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 = defaultdict(int)

for a in A:
    d[a] += 1
S = sum(A)

for q in range(Q):
    b = B[q]
    c = C[q]
    if d[b]==0:
        print(S)
    else:
        S -= d[b]*b
        S += c*d[b]
        d[c] += d[b]
        d[b] = 0
        print(S)

Submission status: Accepted

Solution code:
import collections


def main():
    _ = int(input())
    A = list(map(int, input().split()))
    q = int(input())

    CNT = [0] * (10 ** 5)

    C = collections.Counter(A)
    for k, v in C.items():
        CNT[k - 1] = v

    s = 0
    for i in range(10 ** 5):
        s += (i + 1) * CNT[i]

    # S = []
    for i in range(q):
        b, c = map(int, input().split())
        value = CNT[b - 1]
        CNT[b - 1] = 0
        CNT[c - 1] += value

        s = s - b * value + c * value
        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())
bcs=[list(map(int,input().split())) for i in range(Q)]
total=sum(A)
c=collections.Counter(A)
ans=[0 for i in range(Q)]


for i in range(Q):
    B=bcs[i][0]
    C=bcs[i][1]
    if c[B]!=0:
        total+=c[B]*(C-B)
        ans[i]=total
        c[C]+=c[B]
        c[B]=0
    else:
        ans[i]=total
for i in range(Q):
    print(ans[i])

Submission status: Accepted

Solution code:
import collections
input()
math_dic = collections.Counter((map(int,input().split())))
num = int(input())
total_num = sum([index*value for index,value in math_dic.items()])
for i in range(num):
    a,b = map(int,input().split())
    if a not in math_dic:
        print(total_num)
        continue
    if b not in math_dic:
        math_dic[b] = 0
    total_num -= a*math_dic[a]
    total_num += b*math_dic[a]
    math_dic[b] += math_dic.pop(a)
    print(total_num)