本文共 1044 字，大约阅读时间需要 3 分钟。

考虑用树状数组求解，简单的暴力会超时。

如何求呢？

用树状数组保存每个数出现的次数。

#include
   
    using namespace std;typedef long long ll;const int maxn = 1e6+5;ll a[maxn],b[maxn];ll tr[maxn];int n;void update(int a,int b){       for(int i=a;i<=maxn;i+= (i&-i) ) tr[i] += b;}ll query(int x){       ll res = 0;    for(int i=x;i;i -= (i&-i)) res += tr[i];    return res;}int main(){       cin>>n;    for(int i=1;i<=n;i++) cin>>a[i];    for(int i=1;i<=n;i++)    {           update(a[i],1);        b[i] += i - query(a[i]);//比当前数大的个数        // cout<
    
     <<'\n';    }    memset(tr,0,sizeof(tr));    for(int i=n;i>=1;i--)    {           update(a[i],1);        b[i] += query(a[i]-1);//比当前数小的个数        // cout<
     
      <<'\n';    }    ll ans = 0;    for(int i=1;i<=n;i++)    {           ans += b[i]*(b[i]+1)/2;    }    cout<
      
       <<'\n';    return 0;}