| 123456 |
- #include <iostream>
- #include <unordered_map>
- #include <vector>
- using namespace std;
- struct BIT{vector<int>t;explicit BIT(int n):t(n+1){}void add(int x,int v){for(;x<(int)t.size();x+=x&-x)t[x]+=v;}int sum(int x){int s=0;for(;x;x-=x&-x)s+=t[x];return s;}};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n;cin>>n;vector<long long>a(n);for(auto&x:a)cin>>x;vector<int>L(n),R(n);unordered_map<long long,int>c;for(int i=0;i<n;++i)L[i]=++c[a[i]];c.clear();for(int i=n-1;i>=0;--i)R[i]=++c[a[i]];BIT bit(n);for(int x:R)bit.add(x,1);long long ans=0;for(int i=0;i<n;++i){bit.add(R[i],-1);ans+=bit.sum(L[i]-1);}cout<<ans<<'\n';}
|
