树状数组 + 桶排序的思想

时间复杂度$O(nlogn)$

参考

这篇题解对树状数组的解释很棒，但后半部分稍稍绕了圈子。
其实循环内每次只需ask一次即可。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
typedef long long ll;

int t[N], n;
ll ans1,ans2;

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

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

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int y;
    ll l1, r1, l2, r2;
    cin>>n;
    for(int i = 1; i<=n; i++) {
        cin>>y;
        add(y, 1);
        l2 = ask(y-1);
        r2 = y-1-l2;
        ans2 += l2*r2;

        l1 = i-1-l2;
        r1 = n-y-l1;
        ans1 += l1*r1;
    }

    cout<<ans1<<" "<<ans2<<endl;

    return 0;
}

python代码

N = 200005
t = [0] * N

ans1 = 0
ans2 = 0

n = int(input())
x = list(map(int, input().split()))

def lowbit(x):
    return x & -x

def add(x, k):
    while x <= n:
        t[x] += k
        x += lowbit(x)

def ask(x):
    res = 0
    while x > 0:
        res += t[x]
        x -= lowbit(x)
    return res

for i in range(n):
    y = x[i]
    add(y, 1)

    l2 = ask(y - 1)
    r2 = y - 1 - l2
    ans2 += l2 * r2

    l1 = i - l2
    r1 = n - y - l1
    ans1 += l1 * r1

print(ans1, ans2)