solution.cpp

#include <iostream>
#include <cstring>

using namespace std;
typedef long long LL;
const int N = 1e6 + 10;
int h[N], s[N], tr[N]; //h高，s多少个大于h[i]和小于h[i]的人,tr树状数组
int n;

int lowbit(int x) { return x & -x; }
int add(int x)
{
    for (int i = x; i < N; i += lowbit(i))
        tr[i]++;
} //这里不是添加值，支持计算次数，所以自增1
int q(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        res += tr[i];
    return res;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> h[i], h[i]++; //树状数组必须从1开始

        s[i] = q(N - 1) - q(h[i]); //比i大的数
        add(h[i]);
    }

    memset(tr, 0, sizeof tr); //tr清零重复使用

    for (int i = n - 1; i >= 0; i--)
        s[i] += q(h[i] - 1), add(h[i]); //逆序比较//比h[i]小的数

    LL res = 0;
    for (int i = 0; i < n; i++)
        res += (LL)s[i] * (s[i] + 1) / 2; //公式计算 累加 因为过大所以用LL
    cout << res;

    return 0;
}