离散化 + 树状数组 + 高精度

大佬们已经给出详细的证明，我就不再证明了。 注意这题会爆long long，所以我直接打了一个高精度加法。

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define x first
#define y second
const int maxn = 1000010;
typedef pair<int,int> PII;
typedef long long LL;
PII a[maxn];
int b[maxn];
LL tr[maxn];
int n;
int lowbit(int x)
{
    return x & -x;
}
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}
LL sum(int x)
{
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}
vector<int> Add(vector<int> &a, vector<int> &b)
{
    vector<int> res;
    int t = 0;
    for(int i = 0; i < a.size() || i < b.size(); i ++){
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        res.push_back(t % 10);
        t /= 10;
    }
    if(t) res.push_back(1);
    return res;
}
int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i].x);
        a[i].y = i;
    }
    sort(a + 1,a + n + 1);
    for(int i = 1; i <= n; i ++){
        b[a[i].y] = i;
    }
    vector<int> res;
    res.push_back(0);
    for(int i = 1; i <= n; i ++){
        int y = b[i];
        LL temp = (sum(n) - sum(y)) * (LL)(n - i + 1);
        add(y, i);
        string num = to_string(temp);
        vector<int> temp2;
        for(int j = num.size() - 1; j >= 0; j --) temp2.push_back(num[j] - '0');
        res = Add(res, temp2);
    }
    for(int i = res.size() - 1; i >= 0; i -- ) cout << res[i];
    return 0;
}