[AtCoder] ABC 171 D – Replacing

2020年12月14日

問題

方針

数列の要素の頻度を管理することで、各操作における偏差が計算できます。偏差が計算できれば、操作後の数列の総和を求められます。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    int l = 100001;
    ll v[l]{};
    ll A[N];
    ll s = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        v[A[i]]++;
        s += A[i];
    }
    int Q;
    cin >> Q;
    ll B[Q], C[Q];
    for (int i = 0; i < Q; i++) {
        cin >> B[i] >> C[i];
    }
    for (int i = 0; i < Q; i++) {
        ll e = C[i] * v[B[i]] - B[i] * v[B[i]];
        s += e;
        v[C[i]] += v[B[i]];
        v[B[i]] = 0;
        cout << s << "\n";
    }
    return 0;
}