貌似大家都用的树状数组，我就写一个归并排序版的吧。

算法1

(归并排序) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>

#define ll long long
using namespace std;
const int N = 2e5 + 10;
int g[N], a[N], b[N], c[N], l1[N], r1[N], n;
ll ans1, ans2;

void mergel(int l, int mid, int r) {
    if (l == r)return;
    if (l + 1 == r) {
        if (a[l] > a[r]) {
            l1[a[r]]++;
            swap(a[l], a[r]);
        }
        return;
    }
    mergel(l, (l + mid) >> 1, mid);
    mergel(mid + 1, (mid + 1 + r) >> 1, r);
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++)
        if (j > r || (i <= mid && a[i] <= a[j]))c[k] = a[i++];
        else l1[a[j]] += mid - i + 1, c[k] = a[j++];
    for (int k = l; k <= r; k++)a[k] = c[k];
}

void merger(int l, int mid, int r) {
    if (l == r)return;
    if (l + 1 == r) {
        if (b[l] > b[r]) {
            r1[b[r]]++;
            swap(b[l], b[r]);
        }
        return;
    }
    merger(l, (l + mid) >> 1, mid);
    merger(mid + 1, (mid + 1 + r) >> 1, r);
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++)
        if (j > r || (i <= mid && b[i] <= b[j]))c[k] = b[i++];
        else r1[b[j]] += mid - i + 1, c[k] = b[j++];
    for (int k = l; k <= r; k++)b[k] = c[k];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &g[i]);
    memcpy(a, g, sizeof(g));
    memcpy(b, a, sizeof(b));
    reverse(b + 1, b + 1 + n);
    mergel(1, (1 + n) >> 1, n);
    merger(1, (1 + n) >> 1, n);
    for (int i = 1; i <= n; i++) {
        ans1 += 1ll * l1[g[i]] * r1[g[i]];
        ans2 += 1ll * (i - 1 - l1[g[i]]) * (n - i - r1[g[i]]);
    }
    cout << ans1 << ' ' << ans2;
    return 0;
}

算法2

(树状数组) $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>

#define ll long long
#define lowbit(x) ((x)&(-(x)))
using namespace std;
const int N = 2e5 + 10;
int l[N], r[N];
int t[N], a[N], n;
ll ans1, ans2;

inline int ask(int x) {
    int res = 0;
    for (; x; x -= lowbit(x))res += t[x];
    return res;
}

inline void add(int x, int y) {
    for (; x <= n; x += lowbit(x))t[x] += y;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    for (int i = n; i; i--) {
        r[i] = ask(a[i] - 1);
        add(a[i], 1);
    }
    reverse(a + 1, a + 1 + n);
    memset(t, 0, sizeof(t));
    for (int i = n; i; i--) {
        l[n - i + 1] = ask(a[i] - 1);
        add(a[i], 1);
    }
    for (int i = 1; i <= n; i++)
        ans1 += 1ll * (i - 1 - l[i]) * (n - i - r[i]), ans2 += 1ll * l[i] * r[i];
    cout << ans1 << ' ' << ans2;
    return 0;
}