ABC171 D - Replacing - あっとのTECH LOG

問題原文

解法

愚直にやると当然間に合わない。
あらかじめ全要素の和を計算しておいて、差分更新だけするようにやれば間に合う。
差分更新は各数の個数を持っておけばできる。

実装

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)

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

こういうのは Counter の十八番。
b の個数が0になるのでちょっと注意。
要素数も持つUnionFindでもできそうですね。

感想

PASTに出そう。