分析

本题关键是求当前数h[i]

1. 左边比h[i]大的个数
2. 右边比h[i]小的个数

C++ 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N= 1e6+10;
int h[N],tr[N];     //h数组存储小朋友的身高
int n,sum[N];
LL ans;
int lowbit(int x)
{
    return x&-x;
}
void add(int x,int k)
{
    for(int i=x;i<=N;i+=lowbit(i)) tr[i]+=k;
}
int query(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++) scanf("%d",&h[i]),h[i]++;

    for(int i=0;i<n;i++)    //从左到右找比这个小朋友高的人数
    {
        sum[i]+=query(N-1)-query(h[i]);
        add(h[i],1);    //把这个小朋友的身高加入树状数组
    }

    memset(tr,0,sizeof tr);
    for(int i=n-1;i>=0;i--) //从最右边的小朋友找比这个小朋友矮的人数
    {
        sum[i]+=query(h[i]-1);
        add(h[i],1);
    }
    for(int i=0;i<n;i++) ans+=((LL)sum[i]*(sum[i]+1)/2);    //等差数列求和
    cout<<ans;
    return 0;
}