| 123456 |
- #include <algorithm>
- #include <iostream>
- #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),v;for(auto&x:a)cin>>x;v=a;sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());vector<int>l(n),r(n);BIT bit(v.size());for(int i=0;i<n;++i){int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;l[i]=i-bit.sum(x);bit.add(x,1);}bit=BIT(v.size());for(int i=n-1;i>=0;--i){int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;r[i]=bit.sum(x-1);bit.add(x,1);}long long ans=0;for(int i=0;i<n;++i)ans+=1LL*l[i]*r[i];cout<<ans<<'\n';}
|
