Edit

【pythonでABC171を解説】D - Replacing

問題概要

問題ページ

D - Replacing
D - Replacing

問題ページへ移動する

問題文

あなたは、\(N\) 個の正整数 \(A_{1}, A_{2}, \cdots, A_{N}\) からなる数列 \(A\) を持っています。

あなたは、これから以下の操作を \(Q\) 回、続けて行います。

  • \(i\) 回目の操作では、値が \(B_{i}\) である要素すべてを \(C_{i}\) に置き換えます。

すべての \(i\) \((1 \leq i \leq Q)\) に対して、\(i\) 回目の操作が行われた後の数列 \(A\) のすべての要素の和、\(S_{i}\) を求めてください。

制約

  • 入力は全て整数
  • \( 1 \leq N, Q, A_{i}, B_{i}, C_{i} \leq 10^{5} \)
  • \( B_{i} \neq C_{i} \)

問題の考察

ACコード

import sys
import collections


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    s = sum(a)
    a = collections.Counter(a)
    q = int(input().rstrip('\n'))
    for _ in range(q):
        b, c = list(map(int, input().rstrip('\n').split()))
        s += (c - b) * a[b]
        a[c] += a[b]
        a[b] = 0
        print(s)


if __name__ == '__main__':
    solve()

-Edit
-