# Untitled

user_5668965
c_cpp
17 days ago
1.7 kB
0
Indexable
Never
```#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
struct BIT {
vector<int> bit;  // binary indexed tree
int n;

BIT(int n) {
this->n = n;
bit.assign(n, 0);
}

BIT(vector<int> a) : BIT(a.size()) {
for (size_t i = 0; i < a.size(); i++)
}

int sum(int r) {
int ret = 0;
for (; r >= 0; r = (r & (r + 1)) - 1)
ret += bit[r];
return ret;
}

int sum(int l, int r) {
return sum(r) - sum(l - 1);
}

void add(int idx, int delta) {
for (; idx < n; idx = idx | (idx + 1))
bit[idx] += delta;
}
};

void solve(){
int n;
cin>>n;
int a[n]={};
set<int> st;
for(int i=0;i<n;i++) cin>>a[i],st.insert(a[i]);
int cnt=1;
map<int,int> mapi;
for(auto &it:st){
mapi[it]=cnt++;
}
for(int i=0;i<n;i++) a[i]=mapi[a[i]];
int lefti[n]={};
BIT b1(cnt+5);
for(int i=n-1;i>=0;i--){
lefti[i]=b1.sum(a[i]-1);
}
reverse(a,a+n);
int righti[n]={};
BIT b2(cnt+5);
for(int i=n-1;i>=0;i--){
righti[i]=b2.sum(a[i]+1,cnt+3);
}
reverse(righti,righti+n);
int ans=0;
for(int i=0;i<n;i++){
ans+=(lefti[i]*righti[i]);
}
cout<<ans<<'\n';

}

signed main() {
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
fast
int t=1;
//cin>>t;
while(t--)
solve();
return 0;
}```