并查集

忽略全局加，实际上只有一种操作：把所有指定价格的物品统一修改为另一种价格。

使用 unordered_map 记录每个值的出现次数，然后做完了，赫赫。

时间复杂度 $O(n+q)$。

#include<bits/stdc++.h>
using namespace std;
unordered_map<long long,int> m;
long long ans,add;
int n,q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        static int x;
        cin>>x,++m[x],ans+=x;
    }
    cin>>q;
    for(int i=1;i<=q;i++){
        static string s;
        static int x,y;
        cin>>s;
        if(s[0]=='I') cin>>x,add+=x;
        else{
            cin>>x>>y;
            if(m.count(x-add)&&x!=y){
                ans+=1ll*m[x-add]*(y-x);
                m[y-add]+=m[x-add];
                m[x-add]=0;
            }
        }
        cout<<ans+add*n<<'\n';
    }
    return 0;
}