ABC171 D - Replacing

atcoder.jp 制約がQ <= 10⁵なので，各クエリをO(1)で処理する必要がある．
i回目の操作でO(1)で総和を求められるように，

• あらかじめ，Aの総和ansを求めておく
• A中の各数字の個数を保持しておく（下のコードではリストlに保持している）

BをCに置き換えるという各クエリは， B_count = l[B] l[B] = 0 I[C] = B_count で処理できる．

また，各クエリに対する答えは ans += (C-B)*B_count でも求められる．

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

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

ans = sum(A)
for i in range(Q):
    B, C = list(map(int, input().split()))
    dif = C - B
    
    B_count = l[B]
    l[B] = 0
    l[C] += B_count
    
    ans += B_count * dif
    print(ans)