看着题意：[1,i]中等于a[i]的个数要大于[,jn]中等于a[j]的个数 且iint n;int aa[1000000 + 55];int bb[1000000 + 55];int c[1000000 + 55];map<int ,int > mp;ll lowbit(ll x) { return x&(-x);}void add(int i,int val) { while(i <= n) { c[i] += val; i += lowbit(i); }}ll get_sum(int i) { ll sum = 0; while(i) { sum += c[i]; i -= lowbit(i); } return sum;}void init() { memset(c,0,sizeof(c)); memset(aa,0,sizeof(aa)); memset(bb,0,sizeof(bb)); mp.clear();}int main() { while(scanf("%d",&n) == 1) { init(); for(int i=1;i<=n;i++)scanf("%d",&aa[i]); for(int i=1;i<=n;i++) { mp[aa[i]]++; bb[i] = mp[aa[i]]; add(bb[i],1); } mp.clear(); ll ans = 0ll; for(int i=n;i>=1;i--) { add(bb[i],-1); mp[aa[i]]++; int tmp = mp[aa[i]]; ans += i - get_sum(tmp) - 1; } cout<<ans<<endl; } return 0;}
HTML怎么学习？HTML怎么入门？HTML在哪学？HTML怎么学才快？不用担心，这里为大家提供了HTML速学教程(入门课程)，有需要的小伙伴保存下载就能学习啦！
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号
868
收藏
