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()))
Ad, ans = {}, sum(A)
for a in A:
    Ad[a] = Ad.get(a, 0) + 1

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

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
a = list(map(int,input().split()))
ans = sum(a)
cnt = collections.Counter(a)
for i in range(int(input())):
  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:
import sys,collections
input = sys.stdin.readline

N=input().rstrip()
A=list(map(int,input().split()))
Ac = collections.Counter(A)
Q = int(input())
for i in range(Q):
    B,C = list(map(int,input().split()))
    nb = Ac[B]
    Ac[C] += Ac[B]
    Ac[B] = 0

    if i==0:
        ans = 0
        for key,val in Ac.items():
            ans += key*val
    else:
        ans +=nb*C - nb*B
    
    print(ans)

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

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

sum = 0
for i in A:
    mem[i-1] += 1
    sum += i

for q in range(Q):
    b = bc[q][0]
    if mem[b-1] != 0:
        c = bc[q][1]
        num = mem[b-1]
        mem[c-1] += num
        mem[b-1] = 0
        sum = sum - num*b + num*c
    print(sum)

Submission status: Accepted

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

Submission status: Accepted

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

counts = [0] * (10 ** 5 + 1)
for ai in a:
    counts[ai] += 1

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

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(x) for x in input().split()]
d = {}
for ele in arr:
    if ele in d:
        d[ele] += 1
    else:
        d[ele] = 1

q = int(input())
s = sum(arr)
while(q>0):
    a,b = [int(x) for x in input().split()]
    if a in d:
        x = d[a]
        s -= int(x*a)
        s += int(x*b)
        d.pop(a)
        if b in d:
            d[b]+=x
        else:
            d[b] = x
    print(s)

    q-=1

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())
#print(B,C)
#print(A)
#a = 0
#for i in range(N):
    #a += A[i]
#print(a)
ls = [0]*100000
for i in A:
    ls[i-1] += 1
#print(ls)
sumA = sum(A)
#print("sumA",sumA)
for j in range(Q):
    #print(B[j]-1)
    #print(ls)
    sumA += (C[j]-B[j])*ls[B[j]-1]
    #print("j","C[j]","B[j]","ls[B[j]]",j,C[j],B[j],ls[B[j]-1])
    ls[C[j]-1] += ls[B[j]-1]
    ls[B[j]-1] = 0
    print(sumA)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(raw_input())
a = [int(x) for x in raw_input().split()]
q = int(raw_input())
op = []
for _ in xrange(q):
    v = raw_input().split()
    op.append([int(x) for x in v])

d = {}
total = 0
for v in a:
    d[v] = d.get(v, 0) + 1
    total += v

for src, dest in op:
    c = d.pop(src, 0)
    d[dest] = d.get(dest, 0) + c
    total += c * (dest - src)
    print total

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)]
l = [0] * 100000
suml = 0
for i in a:
  l[i-1] += 1
  suml += i
for i in bc:
  suml += l[i[0]-1] * (i[1] - i[0])
  l[i[1]-1] += l[i[0]-1]
  l[i[0]-1] = 0
  print(suml)

Submission status: Accepted

Solution code:
import os
import heapq
import sys
import math
import operator
from collections import defaultdict
from io import BytesIO, IOBase


"""def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)"""

"""def pw(a,b):
    result=1
    while(b>0):
        if(b%2==1): result*=a
        a*=a
        b//=2
    return result"""



def inpt():
    return [int(k) for k in input().split()]


def main():
    n=int(input())
    ar=list(map(int,input().split()))
    sm=0
    d=defaultdict(int)
    for i in ar:
        d[i]+=1
        sm+=i
    q=int(input())
    for _ in range(q):
        a,b=map(int,input().split())
        if(a in d):
            ct=d[a]
            d[a]=0
            sm-=ct*a
            sm+=ct*b
            d[b]+=ct
        print(sm)
















BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
q = int(input())
count_a = Counter(a)
total = sum(a)
nums = []
for i in range(q):
    b, c = map(int, input().split())
    if b in count_a:
        tmp = count_a[b]
    else:
        tmp = 0
    total = total - count_a[b] * b + tmp * c
    print(total)
    count_a[c] = count_a[c] + tmp
    count_a[b] = 0

Submission status: Accepted

Solution code:
N = raw_input()
ns = raw_input()
ns = ns.split(' ')

data = {}
for i in ns:
    i = int(i)
    if i in data:
        data[i] += 1
    else:
        data[i] = 1

Q = raw_input()
opr = []
for _ in range(int(Q)):
    tmp = raw_input()
    tmp = tmp.split(' ')
    opr.append([int(tmp[0]), int(tmp[1])])

ans = 0
for k, v in data.iteritems():
    ans += k * v
for op in opr:
    if op[0] not in data:
        print ans
        continue

    old1 = data[op[0]]
    del data[op[0]]

    old2 = 0
    if op[1] in data:
        old2 = data[op[1]]
    ans -= old1 * op[0] + old2 * op[1]

    data[op[1]] = old1 + old2
    ans += data[op[1]] * op[1]

    print ans

Submission status: Accepted

Solution code:

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

val = {}

suss = 0
for i in s:
    if i not in val:
        val[i] = 1
    else:
        val[i] += 1

for k, v in val.items():
    suss += k *v

while q:
    c, d = map(int, input().split())
    # print(c, d)
    if c in val:
        if d in val:
            val[d] += val[c]
        else:
            val[d] = val[c]
        suss -= c * val[c]
        suss += d * val[c]
        del val[c]
    # print(val)


    print(suss)

    q -= 1

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

sumA = 0
num = [0]*100001
for aa in a:
    num[aa] += 1
    sumA += aa

for b, c in bc:
    sumA = sumA + ((c - b) * num[b])
    num[c] += num[b]
    num[b] = 0
    print(sumA)

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

sumA = 0
num = [0]*100100
for aa in a:
    num[aa] += 1
    sumA += aa

for b, c in bc:
    sumA = sumA + ((c - b) * num[b])
    num[c] += num[b]
    num[b] = 0
    print(sumA)

Submission status: Accepted

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

s = {}

for v in a:
  if v in s:
    s[v] += v
  else:
    s[v] = v

p = sum(s.values())

for t in r:
  if t[0] in s:
    n = s[t[0]] // t[0] * t[1]
    p = p - s[t[0]] + n
    if t[1] in s:
      s[t[1]] += n
    else:
      s[t[1]] = n
    del s[t[0]]
  print(p)

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)]
count = [0]*((10**5)+100)
for i in range(len(A)):
  count[A[i]] += 1
sumA = sum(A)
for q in range(Q):
  count[BC[q][1]] += count[BC[q][0]]
  sumA += (BC[q][1] - BC[q][0])*count[BC[q][0]]
  print(sumA)
  count[BC[q][0]] = 0

Submission status: Accepted

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

cs = collections.Counter(a_lst)
res = sum(a_lst)
q = int(input())
for i in range(q):
  b, c = map(int, input().split())
  if b in cs:
    res = res - b * cs[b] + c * cs[b]
    if c in cs:
      cs[c] += cs[b]
      cs[b] = 0
    else:
      cs[c] = cs[b]
      cs[b] = 0
  print(res)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = map(int, input().split())
c = Counter(A)
summ = 0
for k, v in c.items():
    summ += k * v
Q = int(input())
for _ in range(Q):
    B, Q = map(int, input().split())
    summ += Q * c[B] - B * c[B]
    c[Q] += c[B]
    c[B] = 0
    print(summ)

Submission status: Accepted

Solution code:
import itertools
import math
import fractions
import functools
import copy
from collections import deque
from functools import reduce
from decimal import Decimal


def main():
    n = int(input())
    a = list(map(int, input().split()))
    q = int(input())
    bc = []
    for _ in range(q):
        bc.append(list(map(int, input().split())))

    a_i = [0]*(10**5 + 10)
    for num in a:
        a_i[num] += 1

    amount = 0
    for i, num in enumerate(a_i):
        amount += num * i

    for element in bc:
        amount = amount - a_i[element[0]] * \
            element[0] + a_i[element[0]] * element[1]
        a_i[element[1]] += a_i[element[0]]
        a_i[element[0]] = 0

        print(amount)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
ma=10**5
a2=[0]*ma
for ii in a:
  a2[ii-1]+=1

def func(a2):
  r=0
  for jj in range(len(a2)):
     r+= a2[jj]*(jj+1)
  return r

r=func(a2)
q=int(input())
for ii in range(q):
  b,c=map(int,input().split())
  r+=(c-b)*a2[b-1]
  a2[c-1]+=a2[b-1]
  a2[b-1]=0
  print(r)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = sum(A)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    if c not in C.keys():
        C[c] = 0
    if b in C.keys():
        ans += (c-b)*C[b]
        C[c] += C[b]
        C[b] = 0
    print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def main():
    N = int(input())
    A = list(map(int, input().split()))
    adict = {}
    for a in A:
        if a in adict.keys():
            adict[a] += 1
        else:
            adict[a] = 1
    # print(adict)
    sum = 0
    for key, v in adict.items():
        sum += key*v
    # print(sum)
    Q = int(input())
    for i in range(Q):
        B, C = map(int, input().split())
        keys_ = adict.keys()
        if B in keys_ and C in keys_:
            sum = sum - B*adict[B] + C*adict[B]
            adict[C] += adict[B]
            adict[B] = 0
        elif B in keys_:
            sum = sum - B*adict[B] + C*adict[B]
            adict[C] = adict[B]
            adict[B] = 0
        print(sum)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
Ans = 0
num = [0] * 100000
an = list(map(int, input().split()))
for i in range(n):
    num[an[i]-1] += 1
    Ans += an[i]
q = int(input())
for i in range(q):
    bici = list(map(int, input().split()))
    Ans += num[bici[0]-1]*(bici[1]-bici[0])
    num[bici[1]-1] += num[bici[0]-1]
    num[bici[0]-1] = 0
    print(Ans)

Submission status: Accepted

Solution code:
n =int(input())
a = list(map(int,input().split()))
s = sum(a)
x = [0]*1000001
for i in a:
    x[i] +=1

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
d = defaultdict(int)
A = list(map(int, input().split()))
for a in A:
    d[a] += 1
Q = int(input())
ans = 0
for k, v in d.items():
    ans += k * v
for _ in range(Q):
    B, C = map(int, input().split())
    d[C] += d[B]
    ans -= B * d[B]
    ans += C * d[B]
    del d[B]
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np
import sys
from bisect import bisect_right, bisect_left

readline = sys.stdin.readline

# 入力にかかる最大計算量O(NlogN)：クイックソート
N = int(input())
A = np.array(readline().split(), np.int64)
num_array = np.zeros(10**5, np.int64)
for n in A:
    num_array[n-1] += 1

# A_sort = np.sort(A)
A_sum = sum(A)
Q = int(input())
BC = np.array([np.array(readline().split(), np.int64) for n in range(Q)], np.int64)
# BC[N][0,1]

# ここの計算量O(N(logN + logN))
for q in range(Q):
    # A = [BC[q][1] if x==BC[q][0] else x for x in A]
    # A[bisect.bisect_left(A, BC[q][0]):bisect.bisect_right(A, BC[q][0])] = BC[q][1]
    '''
    plus_num = BC[q][1] - BC[q][0]
    left = bisect_left(A_sort, BC[q][0])
    right = bisect_right(A_sort, BC[q][0])
    plus_multiple = right - left
    A_sort[left:right] = BC[q][1]
    A_sort = np.sort(A_sort)
    '''

    '''
    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = np.count_nonzero(A == BC[q][0])
    A[A==BC[q][0]] = BC[q][1]
    '''

    plus_num = BC[q][1] - BC[q][0]
    plus_multiple = num_array[BC[q][0] - 1]
    # リスト内の要素数の更新
    num_array[BC[q][1]- 1] += num_array[BC[q][0] - 1]
    num_array[BC[q][0] - 1] = 0

    A_sum = A_sum + plus_num*plus_multiple
    print(A_sum)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random,resource

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def main():
    n = I()
    a = LI()
    q = I()
    bc = [LI() for _ in range(q)]

    t = sum(a)
    u = collections.Counter(a)
    rr = []
    for b,c in bc:
        s = u[b]
        t += (c-b) * s
        u[b] = 0
        u[c] += s
        rr.append(t)


    return JA(rr, '\n')


print(main())

Submission status: Accepted

Solution code:
import sys
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))

n = ri()
a = rl()
t = sum(a)
cnt_li = [0]*10**5
for i in a:
    cnt_li[i-1] += 1

for _ in range(ri()):
    b, c = rm()
    t += (c-b)*cnt_li[b-1]
    print(t)
    cnt_li[c-1] += cnt_li[b-1]
    cnt_li[b-1] = 0

Submission status: Accepted

Solution code:


def q4():
    _ = input()
    A = [int(i) for i in input().split(" ")]
    Q = int(input())
    bc_list = []
    for i in range(Q):
        bc_list.append([int(i) for i in input().split(" ")])

    da = {}
    sa = 0
    for a in A:
        sa += a
        if a in da:
            da[a] += 1
        else:
            da[a] = 1

    last_sum = sa
    sum_a = []

    for bc in bc_list:
        b = bc[0]
        c = bc[1]
        if b not in da:
            sum_a.append(last_sum)
            continue

        diff = c - b
        count = da[b]
        last_sum = last_sum + diff * count
        sum_a.append(last_sum)

        if c not in da:
            da[c] = da[b]
        else:
            da[c] += da[b]
        del da[b]

    for s in sum_a:
        print(s)


q4()

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
d = dd(int)
N = int(input())
for i in [int(n) for n in input().split()]:
  d[i] = d[i]+1
times = int(input())
summation = sum([ key*value for key, value in d.items() if value > 0])
for i in range(times):
  a, b = [int(n) for n in input().split()]
  summation = summation + (b-a)*d[a]
  d[b], d[a] = d[b] + d[a], 0
  print(summation)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
count = [0 for i in range(110000)]
sum_ = sum(A)
for i in range(N):
  count[A[i]] += 1

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

Submission status: Accepted

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

Submission status: Accepted

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

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

S = sum(A)    
for i in range(Q):
    b = Query[i][0]
    c = Query[i][1]
    S += ((c - b) * ls[b])
    ls[c] += ls[b]
    ls[b] = 0
    print(S)

Submission status: Accepted

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

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

S = sum(A)    
for i in range(Q):
    b = Query[i][0]
    c = Query[i][1]
    S += ((c - b) * ls[b])
    ls[c] += ls[b]
    ls[b] = 0
    print(S)

Submission status: Accepted

Solution code:
n = int(input())

ar = [int(s) for s in input().split()]
q = int(input())

bc = [[] for _ in range(q)]

for i in range(q):
    bc[i] = [int(s) for s in input().split()]

#print(bc)

a_ini = sum(ar)

d = {}
for i in ar:
    d[i] = d.setdefault(i,0) + 1

#print(d)


for i in range(q):
    #print(d)
    b = bc[i][0]
    c = bc[i][1]
    a_ini -= (b-c)*d.setdefault(b,0)
    print(a_ini)
    d[c] = d.setdefault(c,0) + d.setdefault(b,0)
    d[b] = 0

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(1,Q):
    BC.append(list(map(int, input().split())))

num = [0]*10**5

#Aの要素の数を管理するリストnumを作成
for k in range(len(A)):
    num[A[k]-1] += 1

counter = 0 #Biと一致した要素の数
s = sum(A) #合計を初期化

for q in range(Q):
    counter = num[BC[q][0]-1]
    num[BC[q][1]-1] += counter #Ciの数に加える
    num[BC[q][0]-1]=0 #Biと等しい値を0個に
    s += (BC[q][1]- BC[q][0])*counter
    print(s)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.defaultdict(int)
currSum = 0
for a in A:
  count[a] += 1
  currSum += a
Q = int(input())
for _ in range(Q):
  B, C = map(int, input().split())
  currSum += (count[B] * (C - B))
  count[C] += count[B]
  count[B] = 0
  print(currSum)

Submission status: Accepted

Solution code:
from collections import Counter

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

c = Counter(A)
total = sum(A)

Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    v = c.get(B)
    if v:
        c[B] = 0
        c[C] += v
        total += (C-B) * v

    print(total)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
 
def main():
    N = int(readline())
    A = [0] *(10**5+1)
    total = 0
    for a in map(int, readline().split()):
        total += a
        A[a] += 1
 
 
    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().split())
        total += A[b]*(c-b)
        print(total)
        A[c] += A[b]
        A[b] = 0
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
 
def main():
    N = int(readline())
    A = [0] *(10**5+1)
    total = 0
    for a in map(int, readline().split()):
        total += a
        A[a] += 1
 
 
    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().split())
        total += A[b]*(c-b)
        print(total)
        A[c] += A[b]
        A[b] = 0
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 8)

 
def main():
    N = int(readline())
    A = [0] *(10**5+1)
    total = 0
    for a in map(int, readline().split()):
        total += a
        A[a] += 1
 
 
    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().split())
        total += A[b]*(c-b)
        print(total)
        A[c] += A[b]
        A[b] = 0
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7
 
def main():
    N = int(readline())
    A = [0] *(10**5+1)
    total = 0
    for a in map(int, readline().split()):
        total += a
        A[a] += 1
 
 
    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().split())
        total += A[b]*(c-b)
        print(total)
        A[c] += A[b]
        A[b] = 0
 
 
if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

def replace(a, bc):
    hist = Counter(a)
    tot = sum(v * c for v, c in hist.items())

    for b, c in bc:
        if b not in hist or b == c:
            delta = 0
        else:
            bct = hist[b]
            delta = (c - b) * bct 
            del hist[b]
            if c not in hist:
                hist[c] = bct 
            else:
                hist[c] += bct
        tot += delta
        print(tot)

def main():
    N = int(input())
    a = [int(i) for i in input().split()]
    Q = int(input())

    bc = []
    for i in range(Q):
        bc.append((int(i) for i in input().split()))

    replace(a, bc)


main()

Submission status: Accepted

Solution code:
import collections

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

count = dict(collections.Counter(A))

ans = sum(A)

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

        count[b] = 0
    
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
t=sum(l)
y=0
x=[0]*(10**5+1)
for i in range(n):
    x[l[i]-1]+=1
r=int(input())
for i in range(r):
    a,b=map(int,input().split())
    if(x[a-1]>0):
       x[b-1]+=x[a-1]
       print(t+b*x[a-1]-a*x[a-1])
       t=t+b*x[a-1]-a*x[a-1]
       x[a-1]=0
    else:
        print(t)

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)]
cnt = [0 for _ in range(10**5+1)]
sum_a = sum(A)
# print(A)
for i in range(len(A)):
    cnt[A[i]] += 1
    # print(A[i])
    # print(cnt[A[i]])
for bc in BC:
    # print(sum_a)
    # print(cnt.count(bc[0]))
    # print((bc[1]-bc[0])*cnt.count(bc[0]))
    sum_a = sum_a + (bc[1]-bc[0])*cnt[bc[0]]
    print(sum_a)
    cnt[bc[1]] += cnt[bc[0]]
    cnt[bc[0]] = 0

Submission status: Accepted

Solution code:
from collections import Counter

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

A_dic = Counter(A)
A_sum = sum(A)

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

Submission status: Accepted

Solution code:
N=int(input())
S=list(map(int,input().split()))
T = [[0 for j in range(2)] for i in range((10**5)+1)]
Q=int(input())

for i in range(10**5+1):
    T[i][0]=i
ans=0
for i in range(N):
    T[S[i]][1]+=1
    ans+=S[i]
   
 
#print(T)   
#print(ans)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import collections

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
xy = [map(int, input().split()) for _ in range(Q)]
b, c = [list(i) for i in zip(*xy)]

sum_num = sum(A)
counter = collections.Counter(A)

for i in range(Q):
    sum_num -= counter[b[i]]*b[i] #counter[x]でxの個数をカウント
    sum_num += counter[b[i]]*c[i] #cで上書きされたので、c*counter[b]になる
    counter[c[i]] += counter[b[i]]
    counter[b[i]] = 0
    print(sum_num)

Submission status: Accepted

Solution code:
n=int(input(""))
ain=input("").split(" ")
a={1:0,}
c=[]
for i in range(n):
    c+=[int(ain[i])]
s=sum(c)
for i in range(n):
    if (c[i] in a):
        a[c[i]]+=1
    else:
        a[c[i]]=1
q=int(input(""))
c=[]

for i in range(q):
    c=input("").split(" ")
    bb=int(c[0])
    cc=int(c[1])
    if (bb in a and a[bb]!=0):
        s+=(cc-bb)*a[bb]
        if (cc in a):
            a[cc]+=a[bb]
        else:
            a[cc]=a[bb]
        a[bb]=0
                              
    print(s)

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter
n = int(input())
a_ls = [int(i) for i in sys.stdin.readline().split()]
ct = Counter(a_ls)
ans = 0
for k, v in ct.items():
    ans += k * v
q = int(input())
for i in range(q):
    b, c = [int(i) for i in sys.stdin.readline().split()]
    ans += (c - b) * ct[b]
    print(ans)
    ct[c] += ct[b]
    ct[b] = 0

Submission status: Accepted

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