算法1

归并排序，会被卡常

C++ 代码

#include<cstdio>
#include<algorithm>
using namespace std;

#define x first
#define y second

const int N = 100010;

typedef long long LL;

typedef pair<int, int> PII;

PII h[N];

int cnt[N];

int n;

void mergesort(int l, int r)
{
    if(l >= r) return;
    int mid = (l + r) / 2;
    PII bh[N];
    mergesort(l, mid);
    mergesort(mid + 1, r);
    int i = l, j = mid + 1, k = 0;
    int cntl = 0, cntr = 0;
    int sl = mid - l + 1, sr = r - mid;
    while(i <= mid && j <= r)
    {
        if(h[i].x > h[j].x)
        {
            cnt[h[j].y] += sl - cntl;
            bh[k ++ ] = h[j ++ ];
            cntr ++;
        }
        else
        {
            cnt[h[i].y] += cntr;
            bh[k ++ ] = h[i ++ ];
            cntl ++;
        }
    }
    while(i <= mid) 
    {
        cnt[h[i].y] += sr;
        bh[k ++ ] = h[i ++ ];
    }
    while(j <= r) bh[k ++ ] = h[j ++ ];
    for(int i = 0; i < k; ++ i)
        h[l ++ ] = bh[i];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++ i)
    {
        int hi;
        scanf("%d", &hi);
        h[i] = {hi, i};
    }
    mergesort(1, n);
    //for(int i = 1; i <= n; ++ i) printf("%d ", h[i].x);
    //for(int i = 1; i <= n; ++ i) printf("%d ", cnt[i]);
    LL res = 0;

    for(int i = 1; i <= n; ++ i)
        res += (LL)(1ll + cnt[i]) * cnt[i] / 2;
    printf("%lld", res);
    return 0;
}

算法2

树状数组，快得很

C++ 代码

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 100010, M = 1000010;

int cnt[N];

int tr[M];

int h[N];

int n;

int lowbit(int x)
{
    return x & -x;
}

void add(int x, int a)
{
    for(int i = x; i <= M - 1; i += lowbit(i)) tr[i] += a;
}

int sum(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 = 1; i <= n; ++ i) scanf("%d", &h[i]);
    for(int i = 1; i <= n; ++ i)
    {
        cnt[i] += sum(M - 1) - sum(h[i]);
        add(h[i], 1);
    }
    memset(tr, 0, sizeof tr);
    for(int i = n; i >= 1; -- i)
    {
        cnt[i] += sum(h[i] - 1);
        add(h[i], 1);
    }
    LL res = 0;
    for(int i = 1; i <= n; ++ i)
        res += (LL)(cnt[i] + 1) * cnt[i] / 2;
    printf("%lld", res);
    return 0;
}