woc,第一个

# include <bits/stdc++.h>
typedef unsigned long long ull;
#define getchar getchar_unlocked()
#define putchar putchar_unlocked

using  namespace  std ;
const int MX=1e5;
int i,j,k;
int r(){
    int x=0,f=1;
    char c=getchar;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar;}
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^(3<<4)),c=getchar;
    return x*f;
}
void w(int x){
    if(x<0) putchar('-'),x=~(x-1);
    else if(x>9) w(x/10);
    putchar(x%10+'0');
}
class BIT{
    private:
        vector<int>tree;
        int siz;
    public:
        BIT(int s):siz(s){tree.resize(siz+1,0);}
        void upd(int idx,int delta){
            while(idx<=siz){
                tree[idx]+=delta;
                idx+=idx&-idx;
            }
        }
        int que(int idx){
            int res=0;
            while(idx>0){
                res+=tree[idx];
                idx-=idx&-idx;
            }
            return res;
        }
};
int  main ( )
{
    int n;
    cin>>n;
    vector<int>a(n);
    int maxi=0;
    for(i=0;i<n;i++){
        cin>>a[i];
        maxi=max(maxi,a[i]);
    }
    vector<int>les(n);
    BIT bil(maxi);
    for(i=0;i<n;i++){
        les[i]=bil.que(a[i]-1);
        bil.upd(a[i],1);
    }
    vector<int>ril(n);
    BIT bir(maxi);
    for(i=n-1;i>=0;i--){
        ril[i]=bir.que(maxi)-bir.que(a[i]);
        bir.upd(a[i],1);
    }
    long long ct=0;
    for(i=0;i<n;i++) ct+=les[i]*ril[i];
    cout<<ct;
    return  0;
}

时间复杂度:$O(n\log(\max(a))$