fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. long long st[4000007];
  4. int n,a[1000007];
  5. map<int,int> c;
  6. int f[1000007],f1[1000007];
  7. void up(int id,int l,int r,int i,int x) {
  8.   if (l>i||r<i) return ;
  9.   if (l==r&&r==i) {
  10.     st[id]+=x;
  11.     return ;
  12.   }
  13.   int g=(l+r)>>1;
  14.   up(id<<1,l,g,i,x);
  15.   up(id<<1|1,g+1,r,i,x);
  16.   st[id]=st[id<<1]+st[id<<1|1];
  17. }
  18. int get(int id,int l,int r,int u,int v){
  19.   if (l>v||r<u) return 0;
  20.   if (l>=u&&r<=v) return st[id];
  21.   int g=(l+r)>>1;
  22.   return get(id<<1,l,g,u,v)+get(id<<1|1,g+1,r,u,v);
  23. }
  24. int32_t main() 
  25. {
  26.     // freopen("maxsum.inp","r",stdin);
  27.     // freopen("maxsum.out","w",stdout);
  28.     ios_base::sync_with_stdio(0);
  29.     cin.tie(0);
  30.     cin>>n;
  31.     for (int i=1;i<=n;i++) cin>>a[i];
  32.     for (int i=1;i<=n;i++) {
  33.       c[a[i]]++;
  34.       f[i]=c[a[i]];
  35.     }
  36.     c.clear();
  37.     for (int i=n;i>0;i--) {
  38.       c[a[i]]++;
  39.       f1[i]=c[a[i]];
  40.       up(1,1,n,f1[i],1);
  41.     }
  42.     long long ans=0;
  43.     for (int i=1;i<=n;i++) {
  44.       up(1,1,n,f1[i],-1);
  45.       ans+=get(1,1,n,1,f[i]-1);
  46.     }
  47.     cout<<ans;
  48.     return 0;
  49. }
Success #stdin #stdout 0.01s 5640KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OYc8pq
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!