树状数组

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 1e6 + 10;

ll n, num[N], swaptime[N];
ll tr[N];

void add(ll u)
{
    for(ll i = u; i < N; i += (i & -i)) tr[i] ++;
}

ll query(ll u)
{
    ll res = 0;
    for(ll i = u; i; i -= (i & -i)) res += tr[i];
    return res;
}

int main()
{
    ios :: sync_with_stdio(false);
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> num[i],
        add(++num[i]),
        swaptime[i] += query(1e6 + 1) - query(num[i]);
    memset(tr, 0, sizeof tr);

    for(int i = n; i; i --)
        swaptime[i] += query(num[i] - 1),
        add(num[i]);
    ll res = 0;
    for(int i = 1; i <= n; i ++) res += (1 + swaptime[i]) * swaptime[i] / 2;
    cout << res;
}