[AtCoder] ABC 171 D – Replacing
問題
方針
数列の要素の頻度を管理することで、各操作における偏差が計算できます。偏差が計算できれば、操作後の数列の総和を求められます。
コード
#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; }
ディスカッション
コメント一覧
まだ、コメントがありません