蓝桥杯历届试题-小朋友排队 （C++代码）树状数组O(nlogm)算法

双倍经验：https://www.lintcode.com/problem/count-of-smaller-number-before-itself/description?_from=ladder&&fromId=26
建议先把这道题做完之后再来做此题；
    思路：相信看到题目的你第一时间想到的应该是冒泡排序，但是如果冒泡排序的话n <= 1e5 时间复杂度是O(n^2)，这必然会TLE，并且冒泡排序并不能保证移动次数最小。
    我们知道最终从低到高排列，而交换的都是不满足前小后大这一规律，所以我们很容易想到逆序对（i < j && A[i] > A[j])。
    如果能想到逆序对，那么就已经做对一半了。
    小朋友最小交换次数就是该小朋友在（正反逆序对（反：它前面有多少个数大于它； 正：它后面有多少个数小于它））中出现的次数总和，而交换 k 次不高兴程度就增加 k，所以最后每个小朋友的不高兴程度就是 1 ～ k 的累加和。这样只要能统计处该小朋友在所有逆序对
    比如样例（3， 2， 1）
    反逆序对：0，1，2
    正逆序对：2，1，0
    总      和：2，2，2
    最终对每个小朋友的k进行单独的1～k累加就是答案：9
    最后利用高斯算法求每个小朋友逆序对个数的累加和
#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "cstring"
#include "cmath"
#include "algorithm"
#include "queue"
#include "map"
#include "vector"
#include "stack"
#include "set"
#include "climits"
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
const int inf = 0x3f3f3f3f;
const int maxn = 1000010;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
//tree：结点数组，A：每个小朋友的身高，B：逆序对总数
int tree[maxn], A[maxn], B[maxn], n;
int lowbit(int x) {
    return x & -x;
}
void update(int x, int val) {
    while(x < maxn) {
        tree[x] += val;
        x += lowbit(x);
    }
}
int query(int x) {
    int ans = 0;
    while(x) {
        ans += tree[x];
        x -= lowbit(x);
    }
    return ans;
}
int main() {
    n = read();
    for(int i = 0; i < n; ++i) {
        A[i] = read() + 1;
        B[i] = query(A[i]);        //求当前小朋友前面有多少个比自己高的小朋友
        //区间更新，根据差分update(L, val), update(R + 1, -val)
        //得到L = 1, R = A[i]，这里的R本来要 + 1，但是因为我们要更新的是1-A[i] - 1的区间，所以这里R = A[i] - 1 + 1 = A[i]
        update(1, 1);
        update(A[i], -1);
    }
    memset(tree, 0, sizeof tree);    //初始化用过一次的tree
    for(int i = n - 1; i >= 0; --i) {
        B[i] += query(A[i]);    //求当前小朋友后面有多少个比自己矮的小朋友
        update(A[i] + 1, 1);    //这里就不需要R了，只需要L = A[i] + 1即可，不明白的话自己手动模拟一遍就知道了
    }
    ll res = 0;
    for(int i = 0; i < n; ++i) res += (ll)(B[i] + 1) * B[i] / 2;    //高斯算法求 1～B[i] 的累加和
    printf("%lld\n", res);
    return 0;
}