61E - Enemy is weak - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define tp top()
#define F front()
#define ss second
#define ff first
#define MOD 1000000007
#define INF 9999999999999999
using namespace std;
ll n,m,i,j,l,r,p,q,k,x,y,test,c,a[1111111],ans;
vector<ll> tree[2111111];
void build(ll node, ll l, ll r){
    if(l==r){
        tree[node].pb(a[l]);
        return;
    }
    build(node*2,l,(l+r)/2);
    build(node*2+1,(l+r)/2+1,r);
    for(int i=0;i<tree[node*2].size();i++) tree[node].pb(tree[node*2][i]);
    for(int i=0;i<tree[node*2+1].size();i++) tree[node].pb(tree[node*2+1][i]);
    sort(tree[node].begin(),tree[node].end());
}
ll ih(ll node, ll l, ll r, ll L, ll R, ll val){
    if(l>=L && r<=R){
        ll left=0,right=tree[node].size()-1,m;
        if(val<tree[node][left]) return tree[node].size();
        if(val>tree[node][right]) return 0;
        while(right-left>1){
            m=(right+left)/2;
            if(tree[node][m]>val) right=m;
            else left=m;
        }
        if(tree[node][left]>val) return tree[node].size()-left;
        else return tree[node].size()-right;
    }
    if(r<L || l>R) return 0;
    return ih(node*2,l,(l+r)/2,L,R,val)+ih(node*2+1,(l+r)/2+1,r,L,R,val);
}
ll baga(ll node, ll l, ll r, ll L, ll R, ll val){
    if(l>=L && r<=R){
        ll left=0,right=tree[node].size()-1,m;
        if(val<tree[node][left]) return 0;
        if(val>tree[node][right]) return tree[node].size();
        while(right-left>1){
            m=(right+left)/2;
            if(tree[node][m]>val) right=m;
            else left=m;
        }
        if(tree[node][right]<val) return right+1;
        else return left+1;
    }
    if(r<L || l>R) return 0;
    return baga(node*2,l,(l+r)/2,L,R,val)+baga(node*2+1,(l+r)/2+1,r,L,R,val);
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(i=1;i<=n;i++) cin>>a[i];
    build(1,1,n);
    for(i=2;i<n;i++) ans+=(ih(1,1,n,1,i-1,a[i])*baga(1,1,n,i+1,n,a[i]));
    cout<<ans;
}