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:
import sys
from collections import Counter

input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    Q = int(input())
    BC = [None] * Q
    for i in range(Q):
        BC[i] = map(int, input().split())

    c = Counter(A)
    d = dict(c.items())
    S = sum(k * v for k, v in c.items())
    for B, C in BC:
        if B in d:
            v = d[B]
            if C in d:
                d[C] += v
            else:
                d[C] = v
            d[B] = 0
            S = S + (C - B) * v
        print(S)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import math
import os
import itertools
import string
import heapq
import _collections
from collections import Counter
from collections import defaultdict
from collections import deque
from functools import lru_cache
import bisect
import re
import queue
import decimal


class Scanner():
    @staticmethod
    def int():
        return int(sys.stdin.readline().rstrip())

    @staticmethod
    def string():
        return sys.stdin.readline().rstrip()

    @staticmethod
    def map_int():
        return [int(x) for x in Scanner.string().split()]

    @staticmethod
    def string_list(n):
        return [Scanner.string() for i in range(n)]

    @staticmethod
    def int_list_list(n):
        return [Scanner.map_int() for i in range(n)]

    @staticmethod
    def int_cols_list(n):
        return [Scanner.int() for i in range(n)]


class Math():
    @staticmethod
    def gcd(a, b):
        if b == 0:
            return a
        return Math.gcd(b, a % b)

    @staticmethod
    def lcm(a, b):
        return (a * b) // Math.gcd(a, b)

    @staticmethod
    def divisor(n):
        res = []
        i = 1
        for i in range(1, int(n ** 0.5) + 1):
            if n % i == 0:
                res.append(i)
                if i != n // i:
                    res.append(n // i)
        return res

    @staticmethod
    def round_up(a, b):
        return -(-a // b)

    @staticmethod
    def is_prime(n):
        if n < 2:
            return False
        if n == 2:
            return True
        if n % 2 == 0:
            return False
        d = int(n ** 0.5) + 1
        for i in range(3, d + 1, 2):
            if n % i == 0:
                return False
        return True

    @staticmethod
    def fact(N):
        res = {}
        tmp = N
        for i in range(2, int(N ** 0.5 + 1) + 1):
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            if cnt > 0:
                res[i] = cnt
        if tmp != 1:
            res[tmp] = 1
        if res == {}:
            res[N] = 1
        return res


def pop_count(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


MOD = int(1e09) + 7
INF = int(1e15)


def solve():
    N = Scanner.int()
    D = [0 for _ in range(10 ** 5 + 10)]
    A = Scanner.map_int()
    for a in A:
        D[a] += 1
    S = sum(A)
    Q = Scanner.int()
    for _ in range(Q):
        b, c = Scanner.map_int()
        x = D[b] * b
        S -= x
        y = D[b] * c
        D[c] += D[b]
        D[b] = 0
        S += y
        print(S)


def main():
    # sys.stdin = open("sample.txt")
    # T = Scanner.int()
    # for _ in range(T):
    #     solve()
    # print('YNeos'[not solve()::2])
    solve()


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
count=[0]*(10**5)
total=sum(A)
for a in A:
    count[a-1]+=1
Q=int(input())
for q in range(Q):
    B,C=map(int,input().split())
    total+=count[B-1]*(C-B)
    if count[B-1]!=0:
        count[C-1]+=count[B-1]
        count[B-1]=0
    print(total)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
As = list(map(int, input().split()))
counter = Counter(As)
ans = 0
for k,v in counter.items():
  ans += k*v

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

Submission status: Accepted

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

res = 0
for k, v in cnt.items():
    res += k*v

for _ in range(int(input())):
    B, C = map(int, input().split())
    res -= cnt[B]*B
    res += cnt[B]*C

    cnt[C] += cnt[B]
    cnt[B] = 0
    print(res)

Submission status: Accepted

Solution code:
import sys
from collections import Counter
input = sys.stdin.readline
N = int(input())
A = [int(i) for i in input().split()]
Q = int(input())
BC = [[int(i) for i in input().split()] for _ in range(Q)]

S = sum(A)
C = Counter(A)
for b, c in BC:
    if b in C:
        if c not in C:
            C[c] = 0
        C[c] += C[b]
        S += (c-b)*C[b]
        C[b] = 0
    print(S)

Submission status: Accepted

Solution code:
n = int(input())
A = tuple(map(int, input().split()))
sa = sum(A)

from collections import Counter
AC = dict(Counter(A))
Q = int(input())
for _ in range(Q):
    f, to = map(int, input().split())
    if f in AC:
        fcount = AC.pop(f)
        AC.setdefault(to, 0)
        AC[to] += fcount
        sa += fcount*(to-f)
    print(sa)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    dic = {}
    for i in range(10**5+10):
        dic[i]=0
    
    s=0
    l = [int(x) for x in input().split()]
    for a in l:
        dic[a]+=1
        s+=a
    ans=[]
    Q = int(input())
    for i in range(Q):
        b,c = map(int,input().split())
        b_num = dic[b]
        dic[b]=0
        dic[c]+=b_num
        s = s + (c-b)*b_num
        ans.append(s)
    for i in ans:
        print(i)
    
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import Counter as cl

def solve(N: int, A: "List[int]", Q: int, B: "List[int]", C: "List[int]"):
    d = [0]*(10**5)
    for ai in A:
        d[ai-1] +=1

    ans = 0
    for i, di in enumerate(d):
        ans += di*(i+1)

    for bi, ci in zip(B,C):
        t_ = d[bi-1]
        ans = ans - bi*t_ + ci*t_
        d[ci-1] += t_
        d[bi-1] = 0
        print(ans)




    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    Q = int(next(tokens))  # type: int
    B = [int()] * (Q)  # type: "List[int]"
    C = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        B[i] = int(next(tokens))
        C[i] = int(next(tokens))
    solve(N, A, Q, B, C)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

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

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

from collections import Counter
C = Counter(A)
C = dict(C)
S = sum(A)
for i in range(q):
    b, c = map(int, input().split())
    if b in C:
        vb = C[b]
        C[b] = 0
        S -= b*vb
        S += c*vb
        print(S)
        if c in C:
            C[c] += vb
        else:
            C[c] = vb
    else:
        print(S)

Submission status: Accepted

Solution code:

N = int(input())

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

dic = {}

s = sum(A)
for i in A:
    if i not in dic:
        dic[i] = 1
    else:
        dic[i] += 1
        

Q = int(input())

for i in range(Q):

    B,C = map(int,input().split())

    if B not in dic:
        pass
    else:

        s -= dic[B] * B
        s += dic[B] * C

        if C not in dic:
            dic[C] = 0

        dic[C] += dic[B]
        dic[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())
queries = []
for i in range(Q):
    Bi, Ci = map(int, input().split())
    queries.append((Bi, Ci))

S = sum(A)
c = Counter(A)
for Bi, Ci in queries:
    S += (Ci - Bi) * c[Bi]
    print(S)
    c.update({Bi: -c[Bi], Ci: c[Bi]})

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    A = list(map(int, rl().split()))
    Q = int(rl())
    B, C = [0] * Q, [0] * Q
    for i in range(Q):
        B[i], C[i] = map(int, rl().split())
    
    counter = Counter(A)
    sum_a = sum(A)
    ans = []
    for b, c in zip(B, C):
        sum_a -= counter[b] * b
        sum_a += counter[b] * c
        counter[c] += counter[b]
        counter[b] = 0
        ans.append(sum_a)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().strip().split()))
q = int(input())
MAX = 1000000 + 1
p = [0] * MAX
si = 0
for i in range(n):
    p[a[i]] += 1
    si += a[i]

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

    if p[b] > 0:
        si = si - b * p[b] + c * p[b]
        p[c] += p[b]
        p[b] = 0

    ans.append(si)

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

Submission status: Accepted

Solution code:
from math import gcd, sqrt, cos, radians, pi
from collections import defaultdict as d

n = int(input())
tab = list(map(int, input().split()))
S = sum(tab)
dico = d(int)
for i in tab:
	dico[i] += 1
q = int(input())
for i in range(q):
	b, c = map(int, input().split())
	s = S - (b * dico[b]) + (c * dico[b])
	dico[c] += dico[b]
	dico[b] = 0
	S = s
	print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    Q = int(input())
    BC = [[int(x) for x in input().split()] for _ in range(Q)]

    cnt = collections.Counter(A)

    ans = sum(A)

    for b, c in BC:
        ans -= cnt[b] * b
        cnt[c] += cnt[b]
        ans += cnt[b] * c
        cnt[b] = 0

        print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
BC = [list(map(int,input().split())) for i in range(Q)]

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

ans = sum(A)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
q=int(input())
from collections import defaultdict
d=defaultdict(int)
for i in range(n):  
  d[A[i]]+=1

ans=sum(A)

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
ans = sum(A)
dic = defaultdict(int) #初期化する関数。
for num in A:
  dic[num] += 1

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

Submission status: Accepted

Solution code:
from collections import Counter

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

Submission status: Accepted

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


def main():
    N = int(readline())
    A = list(map(int, readline().rstrip().split()))
    counter = Counter(A)
    res = sum(A)

    Q = int(readline())
    for _ in range(Q):
        b, c = map(int, readline().rstrip().split())
        res = res - b * counter[b] + c * counter[b]
        counter.setdefault(c, 0)
        counter[c] += counter[b]
        counter.setdefault(b, 0)
        counter[b] = 0

        print(res)
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    n = ni()
    a = na()
    q = ni()

    cnt = collections.Counter(a)

    total = sum(a)
    for _ in range(q):
        b, c = ns()

        if c in cnt.keys():
            cnt[c] += cnt[b]
        else:
            cnt[c] = cnt[b]
        total += (c - b) * cnt[b]
        cnt[b] = 0

        print(total)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#from collections import deque,defaultdict
from sys import stdin
input = stdin.readline
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
a = inl()
q = inn()
h = {}
for x in a:
    if x not in h:
        h[x] = 0
    h[x] += 1
sm = sum(a)
for i in range(q):
    b,c = inm()
    if b not in h:
        print(sm)
    else:
        sm += h[b]*(c-b)
        if c not in h:
            h[c] = 0
        h[c] += h[b]
        h[b] = 0
        print(sm)

Submission status: Accepted

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

tab=[0 for i in range(10**5+1)]

s=0
for ele in A:
    tab[ele]+=1
    s+=ele

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter
def main():
    N = int(input())
    A = list(map(int, input().split()))
    cnt = Counter(A)
    total = sum(A)
    Q = int(input())
    for _ in range(Q):
        B, C = map(int, input().split())
        total = total + (C - B) * cnt[B]
        cnt[C] += cnt[B]
        cnt[B] = 0
        print(total)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    input = sys.stdin.readline
    N = int(input())
    A = Counter([int(x) for x in input().strip().split()])
    Q = int(input())
    ans = sum([k * v for k, v in A.items()])
    for q in range(Q):
        b, c = [int(x) for x in input().strip().split()]
        ans = ans + c * A[b] - b * A[b] 
        A[c] += A[b]
        A[b] = 0
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

d = defaultdict(lambda: 0)
ans = 0
for v in a:
   d[v] += 1
   ans += v
for i in range(q):
   b, c = bc[i]
   if b > c:
      ans -= (b - c) * d[b]
   else:
      ans += (c - b) * d[b]
   d[c] += d[b]
   d[b] = 0
   print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
d = defaultdict(int)
N = int(input())
A = list(map(int,input().split()))
s = 0
ans = []
for i in range(N):
    a = A[i]
    s += a
    d[a] += 1
Q = int(input())
for i in range(Q):
    B,C = map(int,input().split())
    if d[B] == 0:
        ans.append(s)
    else:
        num = d[B]
        d[B] = 0
        d[C] += num
        s += C*num
        s -= B*num
        ans.append(s)
for i in ans:
    print(i)

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()

def main():
    N=ii()
    A = list(mi())

    counter = [0]*(10**5+5)

    for a in A:
        counter[a] += 1

    ans = sum(A)

    Q=ii()
    for q in range(Q):
        B,C=mi()
        ans -= B * counter[B]
        ans += C * counter[B]

        counter[C] += counter[B]
        counter[B] = 0
        print(ans)




if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from decimal import Decimal 		# a = Decimal(a)	# use this for math questions
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(l):
	n = len(l)
	

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
q = int(input())
s = sum(l)
d = dict(Counter(l))
for qq in range(q):
	b,c = list(map(int, stdin.readline().rstrip().split()))
	if(b not in d):
		print(s)
	else:
		s += d[b]*(c-b)
		if(c in d):
			d[c] += d[b]
		else:
			d[c] = d[b]
		d[b] = 0
		print(s)

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:
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
N = int(input())
A = inpl()
D = defaultdict(int)
for a in A:
    D[a] += 1
Q = int(input())
S = sum( k*v for k, v in D.items())
for _ in range(Q):
    B, C = inpl()
    S += (C-B) * D[B]
    D[C] += D[B]
    del D[B]
    print(S)

Submission status: Accepted

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

M = 10**5

memo = [0]*(M+1)

for a in A:
    memo[a] += 1

Q = int(input())

s = sum(i*c for i,c in enumerate(memo))
for _ in range(Q):
    b,c = map(int,input().split())

    cnt = memo[b]
    s += (c-b)*cnt
    memo[c] += memo[b]
    memo[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())
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = Counter(A)
ans = sum(A)
for b, c in X:
    v = ctr[b]
    ans = ans - b * v + c * v
    ctr[b] -= v
    ctr[c] += v
    print(ans)

Submission status: Accepted

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

from collections import defaultdict
from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
# INF = sys.maxsize
INF = 10 ** 10
# INF = float("inf")

count = [0] * (10 ** 5 + 10)


def dp(*x):  # debugprint
    print(*x)


def main():
    N = int(input())
    AS = map(int, input().split())
    sum = 0
    for a in AS:
        count[a] += 1
        sum += a
    Q = int(input())
    for q in range(Q):
        B, C = map(int, input().split())
        sum += (C - B) * count[B]
        count[C] += count[B]
        count[B] = 0
        print(sum)


def _test():
    import doctest
    doctest.testmod()


if __name__ == "__main__":
    import sys
    argv = sys.argv
    if len(sys.argv) == 1:
        # no option
        main()
    elif sys.argv[1] == "-t":
        _test()
    else:
        input = open(sys.argv[1]).buffer.readline

Submission status: Accepted

Solution code:
f=lambda:list(map(int,input().split()))
n,l,q=f()[0],f(),f()[0]
from collections import *
C=Counter(l)
s=sum(k*C[k] for k in C)
for _ in range(q):
  b,c=f()
  v=C[b]
  C[b]-=v
  C[c]+=v
  s+=(c-b)*v
  print(s)

Submission status: Accepted

Solution code:
from collections import Counter

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

cnt = {}
S = sum(A)
for a in A:
    cnt[a] = cnt.get(a,0)+1
for b,c in BC:
    n = cnt.get(b,0)
    S += (c-b)*n
    cnt[b] = 0
    cnt[c] = cnt.get(c,0)+n
    print(S)

Submission status: Accepted

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

d = {}
for a in A:
    if a not in d:
        d[a] = 1
    else:
        d[a] += 1
tmp_sum = sum(A)


for _ in range(Q):
    b, c = list(map(int, input().split()))
    if b in d:
        b_cnt = d[b]
    else:
        b_cnt = 0

    d[b] = 0
    if c in d:
        d[c] += b_cnt
    else:
        d[c] = b_cnt

    sum_diff = (c - b) * b_cnt
    tmp_sum += sum_diff
    print(tmp_sum)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int,input().split()))
q = int(input())
k = collections.Counter(a)
nowsum = sum(a)
for i in range(q):
    b , c = map(int,input().split())
    p = k.get(b,0)
    if p != 0:
        k[c] = k.get(c,0) + p
        k[b] = 0
        nowsum = nowsum - b*p + c*p
    print(nowsum)

Submission status: Accepted

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

S = sum(a)
cnt = Counter(a)
for _ in range(q):
    b, c = map(int, input().split())
    if cnt.get(b):
        ans = S - b*cnt[b] + c*cnt[b]

        if cnt.get(c):
            cnt[c] += cnt[b]
            cnt[b] = 0
        else:
            cnt[c] = cnt[b]
            cnt[b] = 0
        S = ans
    print(S)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import Counter, defaultdict, deque

import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, A, Q, BC):
    ac = Counter(A)
    ans = sum(A)
    for b, c in BC:
        n = ac[b]
        ac[b] = 0
        ac[c] += n
        ans += -n*b + n*c
        print(ans)
    # return ans


def main():
    N = read_int()
    A = read_int_n()
    Q = read_int()
    BC = [read_int_n() for _ in range(Q)]
    slv(N, A, Q, BC)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
 
sys.setrecursionlimit(10 ** 7)
 
from collections import defaultdict
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
# list(map(int, input().split()))

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

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

total = 0
for a in A:
    count[a] += 1
    total += a

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = input().split()
A = [int(x) for x in A]
Q = int(input())
S = sum(A)
L = [0 for _ in range(10**5)]

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

for i in range(Q):
    B,C = map(int,input().split())
    n = L[B-1]
    if n > 0:
        S = S - n*(B-C)
        L[C-1] += n
        L[B-1] = 0
    print(S)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
fwk = BIT(10 ** 5 + 1)
for x in a: fwk.add(x, x)
Q = int(input())
for _ in range(Q):
  b, c = map(int, input().split())
  fwk.add(c, fwk.get(b) // b * c)
  fwk.add(b, -fwk.get(b))
  print(fwk.sum(10 ** 5))

Submission status: Accepted

Solution code:
import collections
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
table = defaultdict(int)
for i in a:
    table[i] += 1
q = int(input())
bc = [tuple(map(int, input().split())) for _ in range(q)]
whole = sum(a)
ans = 0
for b, c in bc:
    if b in table:
        whole = whole + table[b] * (c-b)
        print(whole)
        table[c] += table[b]
        table[b] = 0
    else:
        print(whole)

Submission status: Accepted

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