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:
MAXA = 10 ** 5

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

num = [0 for _ in range(MAXA + 1)]
for a in lista:
    num[a] += 1

s = sum(i * a for i, a in enumerate(num))

for b, c in query:
    n = num[b]

    num[b] = 0
    num[c] += n
    s += n * (c - b)

    print(s)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

from collections import Counter

n = readint()
a = readints()
q = readint()

count = Counter(a)
s = sum(a)

ans = []
for _ in range(q):
    b,c = readints()
    s += (c-b) * count[b]
    ans.append(s)
    count[c] += count[b]
    count[b] = 0
printrows(ans)

Submission status: Accepted

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

    n = int(input())
    A = list(map(int,input().split()))
    q = int(input())
    
    total = sum(A) # これを基に各queryに対応(加算、減算)する
    
    l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
    for _ in A: # 各インデックスに各keyを加算
        l[_] += 1
    
    for i in range(q):
        b, c = map(int,input().split())
        total += c * l[b] # totalの調整のみ
        total -= b * l[b] # 同上
        print(total)
        l[c] += l[b] # ここでリストの更新
        l[b] = 0 # 同上

Replacing()

Submission status: Accepted

Solution code:
from collections import Counter

def Replacing():

    Num = int(input())

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

    Sum = sum(value_A)
    Counter_value = Counter(value_A)

    NumB = int(input())

    for i in range(NumB):
        value_B = list(map(int,input().split()))

        Sum += (value_B[1] - value_B[0])*Counter_value[value_B[0]]
        Counter_value[value_B[1]] += Counter_value[value_B[0]]
        Counter_value[value_B[0]] = 0

        print(Sum)

if __name__ == '__main__':
    Replacing()

Submission status: Accepted

Solution code:
import sys
import collections
input = lambda: sys.stdin.readline().rstrip()

def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    ans = [sum(a)]
    a = dict(collections.Counter(a))
    for i in range(q):
        b, c = map(int, input().split())
        if b in a.keys():
            ans.append(ans[i] + ((c - b) * a[b]))
            if c in a.keys():
                a[c] = a[b] + a[c]
            else:
                a[c] = a[b]
            del a[b]
        else:
            ans.append(ans[i])
    print(*ans[1:], sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a_list=list(map(int,input().split()))
cnt = [0] * int(1e5 + 10)
sum=0
for i in a_list:
 cnt[i] +=1
 sum+=i
  
q=int(input())
ans=0
 
for j in range(q):
 x,y=map(int,input().split())
 sum+=(y-x)*cnt[x]
 cnt[y]+=cnt[x]
 cnt[x]=0
 print(sum)

Submission status: Accepted

Solution code:
n=int(input())
#a,b=map(int,input().split())
al=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
q=int(input())
dic={}
for a in al:
    dic[a]=dic.get(a,0)+1

total=sum(al)
ansl=[]
for i in range(q):
    b,c=map(int,input().split())
    b_num=dic.get(b,0)
    total=total+b_num*(c-b)
    ansl.append(total)
    dic[b]=0
    dic[c]=dic.get(c,0)+b_num

for ans in ansl:
    print(ans)

Submission status: Accepted

Solution code:
def main():
    n, *i = map(int, open(0).read().split())
    a = i[:n]
    _ = i[n]
    s = sum(a)

    m = [0] * (10 ** 5 + 1)
    for x in a:
        m[x] += 1

    ans = []
    for b, c in zip(*[iter(i[n + 1:])] * 2):
        m[c] += m[b]
        s += (c - b) * m[b]
        m[b] = 0
        ans.append(s)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
Q = int(input())
array = []
replace = [0]*(10**5+1)
for i in A:
    replace[i] += 1
sum_s = sum(A)
for i in range(Q):
    m,n = [int(x) for x in input().split()]
    replace[n] += replace[m]

    diff = n*replace[m] - replace[m]*m
    sum_s += diff
    replace[m] = 0
    print(sum_s)

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().split()))
nums = [0] * int(1e5 + 10)
sum = 0
for i in lst:
    nums[i] += 1
    sum += i

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

Submission status: Accepted

Solution code:
n = int(input())
lst = list(map(int, input().split()))
nums = [0] * int(1e5 + 10)
sum = 0
for i in lst:
    nums[i] += 1
    sum += i

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

Submission status: Accepted

Solution code:
def main():
    N, *X = map(int, open(0).read().split())
    A = X[:N]
    Q = X[N]
    s = sum(A)
    B = {}
    for a in A:
        if a not in B:
            B[a] = 0
        B[a] += 1

    ans = []
    for i in range(Q):
        b, c = X[N + 1 + 2*i], X[N + 1 + 2*i + 1]
        if b in B:
            num = B[b]
            s += (c - b)*num
            if c not in B:
                B[c] = 0
            B[c] += num
            B[b] = 0
        ans.append(str(s))
    print('\n'.join(ans))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

if sys.subversion[0] == "PyPy":
    import io, atexit

    sys.stdout = io.BytesIO()
    atexit.register(lambda: sys.__stdout__.write(sys.stdout.getvalue()))

    sys.stdin = io.BytesIO(sys.stdin.read())
    input = lambda: sys.stdin.readline().rstrip()
RS = raw_input
RA = lambda x=int: map(x, RS().split())
RN = lambda x=int: x(RS())


def solve():
    numbers = {}
    for ai in a:
        if not ai in numbers:
            numbers[ai] = 0
        numbers[ai] += 1
    s = sum(a)
    for b, c in bc:
        if b in numbers:
            s = s + (-b + c) * numbers[b]
            if not c in numbers:
                numbers[c] = 0
            numbers[c] += numbers[b]
            del numbers[b]
        print s
    return




n = RN()
a = RA()
q = RN()
bc = [RA() for _ in range(q)]
solve()

Submission status: Accepted

Solution code:
val = [0]*(10**5)
N = int(input())
a = list(map(int, input().split()))
Q = int(input())
ans = sum(a)

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

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
count = Counter(a)
q = int(input())
ans = sum(a)

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

Submission status: Accepted

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

Submission status: Accepted

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

bckt = [0]*(int(1e5)+1)
for i in a:
    bckt[i] += 1
    
s = sum(a)

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

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
a_dic = collections.Counter(A)
Q = int(input())
sum_a = sum(A)
for i in range(Q):
    b, c = list(map(int, input().split()))
    sum_a += (c-b) * a_dic[b]
    if b not in a_dic:
        pass
    else:
        if c not in a_dic:
            a_dic[c] = a_dic[b]
        else:
            a_dic[c] += a_dic[b]
        a_dic[b] = 0
    print(sum_a)

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr: #あらかじめ各Aiの個数を数えておく
 cnt[val]+=1
sums=sum(arr) #あらかじめAiの総和を求めておく
q=int(input())
for _ in range(q):
 b,c=map(int,input().split())
 diff=(c-b)*(cnt[b]) #各クエリにおいて数列Aの総和は(値がBiである要素の個数)*(Ci-Bi)だけ変化する
 sums+=diff
 print(sums) 
 cnt[c]+=cnt[b] #値がCi,Biである要素の個数を更新する
 cnt[b]=0

Submission status: Accepted

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

ans = sum(a)
numbers = [0]*(10**5+1)
for v in a:
    numbers[v] += 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
total = 0
a = list(map(int,input().split()))
table = [0 for i in range(100000+1)]
for i in a:
    total+=i
    table[i]+=1

q = int(input())

for _ in range(q):
    a,b = map(int,input().split())
    total -= table[a]*a
    table[b] += table[a]
    total += table[a]*b
    table[a]= 0
    print(total)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

#N,K = list(map(int, input().split()))
#return chr(64+num)
from collections import Counter

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

dic = Counter(A)

ans = 0
for i in range(max(A)+1):
    ans += i * dic[i]
for i in range(Q):
    ans += dic[B[i]] * (C[i]-B[i])
    print(ans)
    dic[C[i]] += dic[B[i]]
    dic[B[i]] = 0

Submission status: Accepted

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

    S = sum(A)
    Acount = [0] * (10 ** 5 + 1)
    for i in A:
        Acount[i] += 1

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

        S += (C - B) * Acount[B]
        Acount[C] += Acount[B]
        Acount[B] = 0

        print(S)


if __name__ == '__main__':
	main()

exit()

Submission status: Accepted

Solution code:
import numpy as np

N = int(input())
A = np.array([int(a) for a in input().split()])
ans = sum(A)
lst = np.zeros(10**5+1)
for a in A:
    lst[a] += 1
   
for q in range(int(input())):
    B,C = map(int,input().split())
    ans += (C - B) * lst[B]
    print(int(ans))
    lst[C] += lst[B]
    lst[B] = 0

Submission status: Accepted

Solution code:
from sys import *

input = stdin.readline
maxn = 10 ** 5 + 5

Sum = [0] * maxn
Cnt = [0] * maxn

n = int(input())
arr = list(map(int, input().split()))
ans = 0
for x in arr:
	ans += x
	Sum[x] += x
	Cnt[x] += 1 
q = int(input())
result = []
for i in range(q):
	x, y = map(int, input().split())
	ans -= Sum[x]
	ans += y * Cnt[x]
	Sum[y] += y * Cnt[x]
	Cnt[y] += Cnt[x]
	Sum[x] = 0
	Cnt[x] = 0
	result.append(ans)
print('\n'.join(map(str, result)))

Submission status: Accepted

Solution code:
from sys import *

input = stdin.readline
maxn = 10 ** 5 + 5

Sum = [0] * maxn
Cnt = [0] * maxn

n = int(input())
arr = list(map(int, input().split()))
ans = 0
for x in arr:
	ans += x
	Sum[x] += x
	Cnt[x] += 1 
q = int(input())
for i in range(q):
	x, y = map(int, input().split())
	ans -= Sum[x]
	ans += y * Cnt[x]
	Sum[y] += y * Cnt[x]
	Cnt[y] += Cnt[x]
	Sum[x] = 0
	Cnt[x] = 0
	print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
A=list(map(int,input().split()))
q=int(input())
 
counter = Counter(A)
sum_res = sum(A)
for _ in range (q):
       b,af = map(int,input().split())
       sum_res -= b*counter[b]
       sum_res += af*counter[b]
       
       counter[af] += counter[b]
       counter[b] = 0
       print(sum_res)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
def main():
    #入力
    readline=stdin.readline
    n=int(readline())
    a=list(map(int,readline().split()))
    q=int(readline())
    b=[0]*q
    c=[0]*q
    for i in range(q):
        b[i],c[i]=map(int,readline().split())

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

    s=sum(a)

    #クエリ処理
    for i in range(q):
        before=b[i]
        after=c[i]
        s-=before*d[before]
        s+=after*d[before]
        d[after]+=d[before]
        d[before]=0
        print(s)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = [int(w) for w in input().split()]
q = int(input())

a_counter = collections.Counter(a)
now_sum = sum(a)
for i in range(q):
    b, c = [int(w) for w in input().split()]

    num = a_counter[b]
    a_counter[b] = 0
    a_counter[c] += num
    # print(a_counter)

    now_sum += (c - b) * num
    print(now_sum)

Submission status: Accepted

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

s = 0
for i in range(n):
    s += a[i]

import collections
cnt = dict(collections.Counter(a))

for i in range(q):
    b = bc[i][0]
    c = bc[i][1]
    if b in cnt:
        if c in cnt:
            num = cnt[b]
            s += (c - b) * num
            cnt[c] += cnt[b]
            del cnt[b]
        else:
            num = cnt[b]
            s += (c - b) * num
            cnt[c] = num
            del cnt[b]
        print(s)
    else:
        print(s)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))  # (N,)
Q = int(input())
B, C = zip(*[list(map(int, input().split())) for _ in range(Q)])  # (Q,), (Q,)

cur_sum = 0
value_count_map = collections.defaultdict(int)
for a in A:
    cur_sum += a
    value_count_map[a] += 1

for b, c in zip(B, C):
    b_cnt = value_count_map.get(b, 0)
    value_count_map[b] = 0
    value_count_map[c] += b_cnt
    cur_sum += (b_cnt * (c - b))
    print(cur_sum)

Submission status: Accepted

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

C_al = Counter(al)

wa = sum(al)

for i in range(q):
    dt =  bc[i][1]-bc[i][0]
    wa += C_al[bc[i][0]] * dt
    print(wa)
    C_al[bc[i][1]] += C_al[bc[i][0]]
    C_al[bc[i][0]] = 0

Submission status: Accepted

Solution code:
import collections

n=int(input())
arr=list(map(int,input().split()))
cnt=collections.defaultdict(int)
for val in arr:
  cnt[val]+=1
sums=sum(arr)
q=int(input())
for a in range(q):
  b,c=map(int,input().split())
  diff=(c-b)*(cnt[b])
  sums+=diff
  print(sums)
  cnt[c]+=cnt[b]
  cnt[b]=0

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def solve(n, a, q, b, c):
    D = {}
    for x in a:
        if not x in D:
            D[x] = 0
        D[x] += 1
    total = sum(a)
    res = []
    for x, y in zip(b, c):
        if not x in D:
            D[x] = 0
        if not y in D:
            D[y] = 0
        diff = y*(D[x]+D[y]) - (x*D[x] + y*D[y])
        D[x], D[y] = 0, (D[x]+D[y])
        total += diff
        res.append(total)
    return "\n".join(map(str, res))

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())
print(solve(n, a, q, b, c))

Submission status: Accepted

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

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

for i in range(q):
    if number[b[i]] > 0:
        ans += (c[i] - b[i]) * number[b[i]]
        number[c[i]] += number[b[i]]    
        number[b[i]] = 0
    print(ans)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for _ in range(int(input())):
    b, c = map(int, input().split())
    amt = 0
    if b in nums:
        amt = nums.pop(b)
        total -= amt * b
    
    if c in nums:
        nums[c] += amt
    else:
        nums[c] = amt
    total += amt * c
    print(total)

Submission status: Accepted

Solution code:
import collections

n = int(input())
arr = list(map(int, input().split()))
cnt = collections.defaultdict(int)

for val in arr:
    cnt[val] += 1

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

Submission status: Accepted

Solution code:
n=int(input())
g={}
ans=0
for i in map(int,input().split()):
    if g.get(i):g[i]+=1
    else:g[i]=1
    ans+=i
for i in range(int(input())):
    b,c=map(int,input().split())
    if g.get(b):
        cnt=g.pop(b)
        if g.get(c):g[c]+=cnt
        else:g[c]=cnt
        ans-=cnt*b
        ans+=cnt*c
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import collections


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    # 標準入力の取得
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    B, C = [], []
    for q in range(Q):
        B_q, C_q = list(map(int, input().split()))
        B.append(B_q)
        C.append(C_q)

    return N, A, Q, B, C


def main(A: list, B: list, C: list) -> None:
    """
    求解処理.

    Args:\n
        A (list): N個の正整数からなる数列
        B (list): 操作における変換前の値
        C (list): 操作における変換後の値
    """
    # 求解処理
    sum_A = sum(A)
    counter_A = collections.Counter(A)
    for b, c in zip(B, C):
        sum_A += (c - b) * counter_A[b]
        # 結果出力
        print(sum_A)
        # カウンターの更新
        counter_A[c] += counter_A[b]
        counter_A[b] = 0


if __name__ == "__main__":
    # 標準入力を取得
    N, A, Q, B, C = get_input()

    # 求解処理
    main(A, B, C)

Submission status: Accepted

Solution code:
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)

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):
    rep[A[i]] = rep.get(A[i], 0) + 1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cnt_a = Counter(a)
q = int(input())
s = [sum(a)] + [0] * q
for i in range(q):
    b, c = map(int, input().split())
    bn = cnt_a[b]
    s[i + 1] = s[i] + (c - b)*bn
    cnt_a[b] = 0
    cnt_a[c] += bn
print(*s[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict
from sys import stdin, stdout

int_in = lambda: int(stdin.readline())
arr_in = lambda: [int(x) for x in stdin.readline().split()]
mat_in = lambda rows: [arr_in() for _ in range(rows)]
str_in = lambda: stdin.readline().strip()
out = lambda o: stdout.write("{}\n".format(o))
arr_out = lambda o: out(" ".join(map(str, o)))
bool_out = lambda o: out("YES" if o else "NO")
tests = lambda: range(1, int_in() + 1)
case_out = lambda i, o: out("Case #{}: {}".format(i, o))


# https://atcoder.jp/contests/abc171/tasks/abc171_d
def solve(n, a, q, bc):
    buckets = defaultdict(int)
    for item in a:
        buckets[item] += 1
    curr_sum = sum(a)
    result = []
    for b, c in bc:
        curr_sum -= b * buckets[b]
        curr_sum += c * buckets[b]
        buckets[c] += buckets[b]
        buckets[b] = 0
        result.append(curr_sum)
    return result


if __name__ == "__main__":
    n = int_in()
    a = arr_in()
    q = int_in()
    bc = mat_in(q)
    for row in solve(n, a, q, bc):
        out(row)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
cnt_a = Counter(a)
q = int(input())
s = [sum(a)] + [0] * q
for i in range(q):
    b, c = map(int, input().split())
    try:
        cnt_b = cnt_a.pop(b)
        cnt_a[c] += cnt_b
        s[i + 1] = s[i] + (c - b)*cnt_b
    except KeyError:
        s[i + 1] = s[i]
print(*s[1:], sep='\n')

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split()]
dict_a = defaultdict(int)
for i in range(n):
    dict_a[a[i]] += 1
q = int(input())
s = [sum(a)] + [0] * q
for i in range(q):
    b, c = map(int, input().split())
    try:
        cnt_b = dict_a.pop(b)
        dict_a[c] += cnt_b
        s[i + 1] = s[i] + (c - b)*cnt_b
    except KeyError:
        s[i + 1] = s[i]
print(*s[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
q = int(sys.stdin.readline().rstrip())
count_dic = Counter(A)
SUM = sum(A)
for i in range(q):
  b, c = map(int, input().split())
  SUM += count_dic[b]*(c - b)
  count_dic[c] += count_dic[b]
  count_dic[b] = 0
  print(SUM)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
a = list(input().split())
A = [int(a[i]) for i in range(N)]
Q = int(input())
Query = [input().split() for i in range(Q)]
SUM = sum(A)
A_count = Counter(A)
num = [A_count[i+1] for i in range(100000)]

for i in range(Q):
    B = int(Query[i][0])
    C = int(Query[i][1])
    SUM += (C-B) * num[B-1]
    print(SUM)
    num[C-1] += num[B-1]
    num[B-1] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict

d = defaultdict(int)

n = int(input())
a = [int(i) for i in input().split(" ")]
q = int(input())

operations = []

for i in range(q):
    temp = input().split(" ")
    operations.append((int(temp[0]), int(temp[1])))

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

initial_sum = 0
for key, value in d.items():
    initial_sum += key * value

for op in operations:
    target, goto = op

    before = goto * d[goto] + target * d[target]
    d[goto] += d[target]
    d[target] = 0

    after = goto * d[goto]
    diff = after - before
    
    initial_sum += diff
    print(initial_sum)

Submission status: Accepted

Solution code:
N = int(input())

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

L = [0] * 100001
for item in An:
    L[item] += 1

sum = sum(An)

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

Submission status: Accepted

Solution code:
# ans

N = int(input())
A = list(map(int, input().split()))
cnt = [0] * 100001
for i in A:
  cnt[i] += 1
Q = int(input())
S = sum(A)

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*(10**5+1)
sumA = sum(A)
for a in A:
  cnt[a] += 1
        
for query in range(Q):
  b,c = map(int,input().split())
  sumA += cnt[b]*(c-b)
  cnt[c] += cnt[b]
  cnt[b] = 0
  print(sumA)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B=[]
C=[]
for _ in range(Q):
    b,c = map(int,input().split())
    B.append(b)
    C.append(c)
dic = {}
for a in A:
    if a in dic:
        dic[a] += 1
        continue
    dic[a] = 1

ans = 0
for key,val in dic.items():
    ans += key*val

for b,c in zip(B,C):
    if b in dic:
        ans -= dic[b] * b
        ans += dic[b] * c

        if c in dic:
            dic[c] += dic[b]
        else:
            dic[c] = dic[b]
        dic[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Jun 23 21:04:33 2020

@author: naoki
"""

N = int(input()) # input the row A length "N" 
A = list(map(int,input().split())) # input the row of A 
Q = int(input()) # input the number of trying operation 
BC = [list(map(int,input().split())) for i in range(Q)]
S = 0
num = [0 for i in range(100001)] 
for i in A:
    S += i # Sum of all conponents of the row "A"
    num[i]+=1 

for B,C in BC:
    S = S + (C - B) * num[B]
    num[C] += num[B]
    num[B] = 0 
    print(S)

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

import collections
co = collections.Counter(a)

ans = sum(a)

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
bc = [list(map(int, input().split())) for _ in range(q)]
suma = sum(a)
counter = Counter(a)
for b, c in bc:
    suma -= b * counter[b]
    suma += c * counter[b]
    counter[c] += counter[b]
    counter[b] = 0
    print(suma)

Submission status: Accepted

Solution code:
import collections
N=int(input())
A=list(map(int,input().split()))
S=sum(A)
D=collections.Counter(A)
Q=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:
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)]
suma = sum(a)
counter = Counter(a)
for i in range(q):
    suma -= bc[i][0] * counter[bc[i][0]]
    suma += bc[i][1] * counter[bc[i][0]]
    counter[bc[i][1]] += counter[bc[i][0]]
    counter[bc[i][0]] = 0
    print(suma)

Submission status: Accepted

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

# 要素の出現回数をカウント
counter = dict(collections.Counter(A))
# print(counter)
 
for i in range(Q):
    b, c = BC[i]
    if not b in counter:
        counter[b] = 0
    if not c in counter:
        counter[c] = 0
    cnt = counter[b]
    sum_ += (c-b)*cnt
    print(sum_)
    counter[b] -= cnt
    counter[c] += cnt

Submission status: Accepted

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

total = sum(A) # これを基に各queryに対応(加算、減算)する

l = [0 for i in range(10**5+1)] # 配列のインデックスを各valueとみなす
for _ in A: # 各インデックスに各keyを加算
    l[_] += 1

for i in range(q):
    b, c = map(int,input().split())
    total += c * l[b] # totalの調整のみ
    total -= b * l[b] # 同上
    print(total)
    l[c] += l[b] # ここでリストの更新
    l[b] = 0 # 同上

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

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

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