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 defaultdict

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

n = ni()
a = nl()
q = ni()
list_ = defaultdict(lambda: 0)
for i in a:
    list_[i] += 1
res = sum(a)
for i in range(q):
    b,c = nm()
    res = res + (c*(list_[b])-b*list_[b])
    x = list_[b]
    list_[b] = 0
    list_[c] += x

    print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

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

d = Counter(As)
S = sum(k*v for k, v in d.items())
Q = int(input())
for _ in range(Q):
    B, C = map(int, input().split())
    if B in d:
        S += d[B] * (C-B)
        d[C] += d[B]
        d[B] = 0
    print(S)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
q = int(input())
dic = {}
for i in range(n):
  if not a[i] in dic:
    dic[a[i]] = 1
  else:
    dic[a[i]] += 1

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

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    c = [0] * (10**5+1)
    ans = 0
    for x in sys.stdin.readline().split():
        x = int(x)
        c[x] += 1
        ans += x

    Q = NI()
    for _ in range(Q):
        i,j = LI()
        k = c[i]
        ans += (j-i) * k
        c[j] += k
        c[i] = 0
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
from decimal import Decimal
from collections import defaultdict

# import fractions

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    Q = ii()
    cnt = collections.Counter(A)
    sm = sum(A)

    for q in range(Q):
        B, C = il()
        sm += (C - B) * cnt[B]
        print(sm)
        cnt[C] += cnt[B]
        cnt[B] = 0


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
S = [0]*(10**5)

ans = 0
for n in range(N):
    a = A[n]
    S[a-1] += a
    ans += a

Q = int(sys.stdin.readline().rstrip())

for q in range(Q):
    B, C = list(map(int, sys.stdin.readline().rstrip().split()))
    up = C * S[B-1]//B
    down = S[B-1]
    S[C-1] += C * S[B-1]//B
    S[B-1] = 0
    ans = ans + up - down
    print(ans)

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys
input = sys.stdin.readline
ipnl = lambda n: [int(input()) for _ in range(n)]
inp = lambda :int(input())
ip = lambda :[int(w) for w in input().split()]

n = inp()
x = ip()
q = inp()
dt = {}
for i in x: dt[i] = dt.get(i,0)+1
sm = sum(x)
for i in range(q):
    b,c = ip()
    ct = dt.get(b,0)
    if ct == 0:
        print(sm)
        continue
    sm -= ct*b
    sm += ct*c
    print(sm)
    dt[b] = 0
    dt[c] = dt.get(c,0) + ct

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = sum(A)
howmany = [0 for k in range(10**5+1)]
for k in range(N):
    howmany[A[k]] +=1

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    ai = Counter(_ia())
    s = sum(k * v for k, v in ai.items())
    q = _i()
    for _ in range(q):
        b, c = _ia()
        m = ai.get(b, 0)
        s += (c-b) * m
        ai[b] = 0
        ai[c] += m
        print(s)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
A = readInts()
q = I()
dic = Counter(A)
SUM = sum(A)
#print(dic)
for i in range(q):
    b,c = readInts()
    SUM -= b * dic[b]
    SUM += c * dic[b]
    dic[c] += dic[b]
    dic[b] = 0
    print(SUM)
#print(dic)

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()))
    q=int(input())
    BC=[list(map(int,input().split())) for _ in range(q)]
    C=Counter(A)
    ans=sum(A)
    for b,c in BC:
        cnt=C[b]
        ans+=(c-b)*cnt
        C[b]=0
        C[c]+=cnt
        print(ans)
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
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 i in range(Q)]

suma=sum(A)
dicA=defaultdict(int)
for a in A:
    dicA[a]+=1

for b,c in BC:
    D=(c-b)*dicA[b]
    suma+=D
    e=dicA[b]
    dicA[b]=0
    dicA[c]+=e
    print(suma)

Submission status: Accepted

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=LI()
q=I()
cou=Counter(lis)
ans=sum(lis)
for i in range(q):
    b,c=MI()
    x=cou[b]
    #y=cou[c]
    ans+=(c-b)*x
    print(ans)
    cou[c]+=cou[b]
    cou[b]=0

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
ans = sum(a)
key = Counter(a)

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

Submission status: Accepted

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    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)
        
    
    
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
N=int(input())
L=list(map(int,input().split()))
D={}
for i in L:
    if i not in D:
        D[i]=1
    else:
        D[i]+=1

#print(D)

ans=0
for k,v in D.items():
    ans+=k*v
#print(ans)

Q=int(input())

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

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    d = {}
    for i in range(len(arr)):
        if arr[i] in d:
            d[arr[i]] += 1
        else:
            d[arr[i]] = 1
    sums = sum(arr)
    q = int(input())
    for i in range(q):
        b, c = map(int, input().split())
        if b in d:
            sums -= (b * d[b])
            sums += (c * d[b])
        if c not in d and b in d:
            d[c] = d[b]
        elif b in d:
            d[c] += d[b]
        if b in d:
            d[b] = 0
        print(sums)

Submission status: Accepted

Solution code:
from collections import Counter
X = open(0).readlines()
n = int(X[0])
*A, = map(int, X[1].split())
counter = Counter(A)
q = int(X[2])
s = sum(A)
for x in X[3:]:
    b, c = map(int, x.split())
    if b in counter:
        t = counter.pop(b)
        s += c*t - b*t
        counter[c] = counter.get(c, 0) + t
    print(s)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import*
(n,), a, q, *d = [list(map(int, o.split())) for o in open(0)]
C = Counter(a)
s = sum(a)
for b, c in d:
    bf = C[b]
    C[c] += bf
    C[b] = 0
    s += (c - b) * bf
    print(s)

Submission status: Accepted

Solution code:
from collections import Counter

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

counter = Counter(A)
tmp_sum = sum(A)
for i in range(Q):
    B, C = map(int, input().split())
    B_cnt = counter[B]
    counter[B] = 0
    counter[C] += B_cnt
    tmp_sum = tmp_sum + (C - B) * B_cnt
    print(tmp_sum)

Submission status: Accepted

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

from collections import defaultdict

D = defaultdict(int)

res = 0

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

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

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

Submission status: Accepted

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

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

ans = sum(A)

Q = int(input())
for i in range(Q):
    B, C = map(int, input().split())
    value = num_list[B]
    ans = ans - B*value + C*value
    print(ans)
    num_list[B] = 0
    num_list[C] += value
# BC = [list(map(int, input().split())) for _ in range(Q)]

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
cnt = Counter(a)
s = sum(a)
q = I()
for _ in range(q):
    b, c = LI()
    s -= b * cnt[b]
    s += c * cnt[b]
    cnt[c] += cnt[b]
    cnt[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())

counter = Counter(A)
ans = sum(A)
for i in range(Q):
  b, c = map(int, input().split())
  count_b = counter[b]
  counter[b] -= count_b
  counter[c] += count_b
  ans = ans - b*count_b + c*count_b
  print(ans)

Submission status: Accepted

Solution code:
import heapq

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
bc = [[int(i) for i in input().split()] for j in range(q)]

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

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

total = sum(a)

for i in range(q):
    total += (bc[i][1] - bc[i][0]) * dp[bc[i][0]]
    print(total)
    dp[bc[i][1]] += dp[bc[i][0]]
    dp[bc[i][0]] = 0

Submission status: Accepted

Solution code:
from collections import defaultdict
d = defaultdict(int)
N = int(input())
A = list(map(int, input().split()))
for a in A:
    d[a] += 1
s = sum(A)
Q = int(input())

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

N = INT()
A = LIST()
C = Counter(A)

cur = sum(A)
Q = INT()
for _ in range(Q):
    b, c = MAP()
    cur -= b * C[b]
    cur += c * C[b]
    print(cur)
    C[c] += C[b]
    C[b] = 0

Submission status: Accepted

Solution code:
array = [0 for i in range(100001)]
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

for a in A:
    array[a] += 1
souwa = sum(A)

B = []
C = []
for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(Q):
    souwa = souwa + (C[i]-B[i])*array[B[i]]
    array[C[i]] += array[B[i]]
    array[B[i]] = 0
    print(souwa)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
dic1 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))
q = int(readline())
#exist = [0]*(10**5+1)
ans = 0
for i in lst1:
    dic1[i] += 1
    ans += i

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
from math import floor, sqrt, factorial, hypot, log  # log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter, defaultdict, deque
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from copy import deepcopy
from fractions import gcd
from random import randint


def ceil(a, b): return (a + b - 1) // b


inf = float('inf')
mod = 10 ** 9 + 7


def pprint(*A):
    for a in A:     print(*a, sep='\n')


def INT_(n): return int(n) - 1


def MI(): return map(int, input().split())


def MF(): return map(float, input().split())


def MI_(): return map(INT_, input().split())


def LI(): return list(MI())


def LI_(): return [int(x) - 1 for x in input().split()]


def LF(): return list(MF())


def LIN(n: int): return [I() for _ in range(n)]


def LLIN(n: int): return [LI() for _ in range(n)]


def LLIN_(n: int): return [LI_() for _ in range(n)]


def LLI(): return [list(map(int, l.split())) for l in input()]


def I(): return int(input())


def F(): return float(input())


def ST(): return input().replace('\n', '')


def main():
    N = I()
    A = LI()
    Q = I()
    AI = [0]*(10**5+1)
    ans = 0
    for a in A:
        AI[a] += 1

    for i in range(10 ** 5 + 1):
        ans += i * AI[i]
    for _ in range(Q):
        B, C = MI()
        ans = ans - B * AI[B] + C * AI[B]
        AI[C] += AI[B]
        AI[B] = 0
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from math import factorial, sqrt, ceil, gcd
from functools import lru_cache, reduce
from decimal import Decimal
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# UnionFind
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

# ダイクストラ
def dijkstra_heap(s, edge, n):
    #始点sから各頂点への最短距離
    d = [10**20] * n
    used = [True] * n #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

# 素因数分解
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

# 2数の最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

# リストの要素の最小公倍数
def lcm_list(numbers):
    return reduce(lcm, numbers, 1)

# リストの要素の最大公約数
def gcd_list(numbers):
    return reduce(gcd, numbers)

# 素数判定
def is_prime(n):
    if n <= 1:
        return False
    p = 2
    while True:
        if p ** 2 > n:
            break
        if n % p == 0:
            return False
        p += 1
    return True


# limit以下の素数を列挙
def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P

# 同じものを含む順列
def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        # set（集合）型で重複を削除、ソート
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


# ここから書き始める
n = int(input())
a = list(map(int, input().split()))
cnt = [0 for i in range(10 ** 5)]
for i in a:
    cnt[i - 1] += 1
ans = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    ans += c * cnt[b - 1] - b * cnt[b - 1]
    r = cnt[b - 1]
    cnt[b - 1] = 0
    cnt[c - 1] += r
    print(ans)
# print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = [int(a) for a in input().split()]
d = defaultdict(int)
for a in A:
    d[a] += 1
Q = int(input())
S = sum(A)
ans = []
for _ in range(Q):
    B, C = map(int, input().split())
    S += d[B] * (C - B)
    ans.append(S)
    d[C] += d[B]
    d[B] = 0
for a in ans:
    print(a)

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 main():
    N = I()
    A = LI()
    Q = I()
    d = collections.Counter(A)
    ans = []
    cursum = sum(A)
    for i in range(Q):
        b, c = LI()
        cursum -= b * d[b]
        d[c] += d[b]
        cursum += c * d[b]
        d[b] = 0
        ans.append(cursum)
    for a in ans:
        print(a)


main()

Submission status: Accepted

Solution code:
#!usr/bin/env pypy3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect


def LI(): return [int(x) for x in sys.stdin.readline().split()]


def I(): return int(sys.stdin.readline())


def LS(): return [list(x) for x in sys.stdin.readline().split()]


def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res


def IR(n):
    return [I() for i in range(n)]


def LIR(n):
    return [LI() for i in range(n)]


def SR(n):
    return [S() for i in range(n)]


def LSR(n):
    return [LS() for i in range(n)]


sys.setrecursionlimit(1000000)


def main():
    N = I()
    A = LI()
    Q = I()
    BC = [LI() for _ in range(Q)]

    d = defaultdict(int)

    for ai in A:
        d[ai] += 1

    ans = 0
    for (k, v) in d.items():
        ans += k * v

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


main()

Submission status: Accepted

Solution code:
import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

N = ri()
A = rl()
Q = ri()
queries = []
for i in range(Q):
	q = rl()
	queries.append(q)

import collections

cnt = collections.Counter(A)
s = sum(A)

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

Submission status: Accepted

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


num=[]
for i in range(100000+1):
    num.append(0)
for a in As:
    num[a]+=1

sum=0
for number,i in enumerate(num):
    sum+=number*i


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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

from collections import Counter
N = int(input())
As = list(mapint())
Q = int(input())

S = sum(As)
C = Counter(As)
for _ in range(Q):
    b, c = mapint()
    cnt = C[b]
    S += (c-b)*cnt
    C[b] = 0
    C[c] += cnt
    print(S)

Submission status: Accepted

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

r = [0]*(10**5+1)
for i in range(n):
    r[a[i]] += 1
s = sum(a)
for b,c in bc:
    r[c] += r[b]
    s += (c-b)*r[b]
    r[b] = 0
    print(s)

Submission status: Accepted

Solution code:
import collections
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())
 
    
    

N = rri()
arr = rrm()
dic = collections.Counter(arr)
s = sum(arr)
q = rri()
for _ in range(q):
    a, b= rrm()
    s+=dic[a]*(b-a)
    dic[b]+=dic[a]
    del dic[a]
    print(s)

Submission status: Accepted

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

def solve():
    N = int(readline())
    A = list(map(int, readline().split()))
    Q = int(readline())
    BC = [list(map(int, readline().split())) for i in range(Q)]

    count = {}
    for a in A:
        count[a] = count.get(a, 0) + 1
    
    s = sum(A)

    for b, c in BC:
        if b in count:
            nb = count[b]
            diff = (c - b) * nb
            s += diff
            print(s)

            del count[b]
            count[c] = count.get(c, 0) + nb
        else:
            print(s)


solve()

Submission status: Accepted

Solution code:
import collections

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

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

Submission status: Accepted

Solution code:
"""
~~ Author : Bhaskar
~~ Dated : 10~06~2020
"""

import sys
from bisect import *
from math import floor,sqrt,ceil,factorial as F,gcd,pi
from itertools import chain,combinations,permutations,accumulate
from collections import Counter,defaultdict,OrderedDict,deque
from array import array
INT_MAX = sys.maxsize
INT_MIN = -(sys.maxsize)-1
mod = 1000000007
ch = "abcdefghijklmnopqrstuvwxyz"
lcm = lambda a,b : (a*b)//gcd(a,b)
setbit = lambda x : bin(x)[2:].count("1")
input = lambda : sys.stdin.readline()

def solve():
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    d = Counter(a)
    s = sum(a)
    q = int(sys.stdin.readline())
    for _ in range(q):
        b, c = map(int, sys.stdin.readline().split())
        s += d[b]*c - d[b]*b
        d[c] += d[b]
        d[b] = 0
        print(s) 


if __name__ == "__main__":
    try:
        sys.stdin = open('input.txt','r')
        sys.stdout = open('output.txt','w')
    except:
       pass
    solve()

Submission status: Accepted

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

cnt={}
for i in a:
  if i in cnt:
    cnt[i]+=1
  else:
    cnt[i]=1
s=0
for i in cnt:
  s+=i*cnt[i]
  
for i in ql:
  if i[0] in cnt:
    s+=(i[1]-i[0])*cnt[i[0]]
    if i[1] in cnt:
      cnt[i[1]]+=cnt[i[0]]
    else:
      cnt[i[1]]=cnt[i[0]]
    cnt[i[0]]=0
  print(s)

Submission status: Accepted

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


def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    Q = int(input().strip())
    BC = []
    for i in range(Q):
        b, c = map(int, input().strip().split())
        BC.append((b, c))
    return N, A, Q, BC


def solve(N, A, Q, BC):
    D = Counter(A)
    ans = sum(A)
    for b, c in BC:
        if D[b] > 0:
            v = D[b]
            ans -= b * v
            D[b] = 0
            D[c] += v
            ans += c * v
        print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Accepted

Solution code:
N=int(input())
A=[int(i) for i in 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]=map(int,input().split())
D=dict()
for i in range(N):
    if A[i] in D:
        D[A[i]]+=1
    else:
        D[A[i]]=1
S=sum(A)
for i in range(Q):
    if not(B[i] in D):
        print(S)
        continue
    tmp=D[B[i]]
    D[B[i]]=0
    if C[i] in D:
        D[C[i]]+=tmp
    else:
        D[C[i]]=tmp
    S=S+(C[i]-B[i])*tmp
    print(S)