これは似たようなテクをTopCoderで見たことあったので。
https://yukicoder.me/problems/no/885
問題
N要素の整数列Aが与えられる。
以下のクエリに順次答えよ。
- 整数Xが与えられるので、Aの各値をmod Xで置き換える。その都度、Aの総和を答えよ。
解法
Aをmapを使い、値とその登場頻度の対で管理しよう。
各クエリについては、X以上の値を持つものをそれぞれまとめてmod Xの値に置き換え、総和の変分を引いていくとよい。
ここで、P mod QはP/2未満になるので、mod Xでの置き換えは高々O(N*log(max(A)))回しか発生しない。
int N,Q; map<int,int> M; ll sum=0; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>x; M[x]++; sum+=x; } cin>>Q; while(Q--) { cin>>x; while(M.rbegin()->first>=x) { int nx=M.rbegin()->first%x; int ny=M.rbegin()->second; sum-=(M.rbegin()->first-nx)*1LL*ny; M.erase(M.rbegin()->first); M[nx]+=ny; } cout<<sum<<endl; } }
まとめ
塗り絵に手間取りすぎてここら辺ポイントをロスしてるんだよな。