题目：0排序 - 蓝桥云课

思路：要想使数组顺序，那么对于每个数而言，右边每有一个小于自身的数，就必定要右移一次。而它的代价就是：

右边小于它的数的个数*这个数（代价）

那么如果直接去暴力的去找那么时间复杂度我们肯定是接受不了的，那么有没有什么方法能够让我们快速的去找到每个数的右边比它小的数呢？其实我们可以想到将数组从后往前遍历，将每个数组里面的值放到我们的树状数组里面，那么我们每次查询某个数在当前位置有多少个小于自己的数的数量的时间复杂度就直接变成了O（1）的了。（其实当发现元素的大小竟然和数组长度大小差不多时就已经可以先怀疑一手有没有可能会用到把元素映射为树状数组下标的可能性了TUT）

代码：

ll lob(ll x) {
    return x & (-x);
}

void Update(ll i, ll x,vector<ll>& v) {
    ll n = (int)v.size() - 1;
    while (i < n) {
        v[i] += x;
        i += lob(i);
    }
}

int que(vector<ll>& v, ll i) {
    ll sum = 0;
    while (i > 0) {
        sum += v[i];
        i -= lob(i);
    }
    return sum;
}
//以上为树状数组代码
/////////////////////////////////////////////////////

void solve() {
    ll n;
    cin >> n;
    vector<ll> v(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
    }
    vector<ll> vv(1000001);
    ll f = 0;
    for (ll i = n; i >= 1; i--) {
        //将数组的大小变为树状数组的索引
        Update(v[i], 1, vv);
        //v[i] - 1 的原因是只统计比自己小的数
        f += v[i] * que(vv, v[i] - 1);
    }
    cout << f << endl;
}

总结：这道题的代码量不大，但是思考起来确实难受啊...元素映射为数组下标的情况真就写一次卡一次呗。。。