分析

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1000010;

int n;
int h[N], tr[N];
int sum[N];

int lowbit(int x){//取x的最后一位1
    return x& -x;
}
void add(int x,int y){//在x处加上y
    for(int i=x;i<=n;i+=lowbit(i)){
        tr[i]+=y;
    }
}
int query(int x){//查询第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);
    }

    LL res = 0;
    for (int i = 0; i < n; i ++ ) res += (LL)sum[i] * (sum[i] + 1) / 2;

    cout << res << endl;

    return 0;
}