时间复杂度O(NlogN)

一个小朋友要移动多少次和该小朋友的逆序对个数有关 和位置无关
因为最后一定是排成一个从小到大的顺序，此时的逆序对一定为0
所以对于任意一个小朋友的逆序对数量也要减到0，这一步和小朋友的位置无关(忽略只能交换2个相邻小朋友这个条件)
对于2个不相邻的逆序对来说，他们在这一时刻是不能交换的
但是一定有一个时刻他们是相邻的，则可以交换
反证法：
如果没有一个时刻这一对逆序对是相邻的，则他们一辈子都不可能交换
则序列中一定存至少一个逆序对，那么就一定不可能是从低到高排序的
问题变成了求每个小盆友的逆序对个数（和用归并排序求逆序对有点不同）
很显然，一个数的逆序对应该等于=这个数左边比他大的数+右边比他小的数的个数
因为这一题的Hi范围最大是1e6
则可以用前缀和求数组中小于x（大于x）的数的个数 参考第1236题

那么为什么用树状数组不能直接用前缀和呢？

如果用前缀和可以求出大于x的个数，但这个个数是整个数组中大于x的个数
不一定是x左边比x大的个数
所以我们应该动态维护一个序列，从头遍历一遍数组
当遍历到每个数的时候，求一遍比该数大的个数那一定是左边的数
然后再把x加入到序列中，这可能会修改数组，所以要用到树状数组
求右边比本身小的数，只要从后往前遍历即可

如何用前缀和求大于x的数的个数

先用一个数组h存当前这个数左边每种身高的个数
那么大于x的数的个数就等于目前全部数的个数-小于等于x的数的个数
其中小于等于x的数的个数应该等于h数组1到x的前缀和
在树状数组中就是query(x)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1e6 + 10;
int a[N];  //原数组
int h[N];  //这个数组用来存每个高度的个数 h[i]表示i这个高度的的小朋友个数
int tr[N];  //树状数组
int cnt[N];  //cnt[i]表示第i个小朋友的逆序对个数，即他要移动的步数
int n;
int lowbit(int x){
    return x & -x;
}
void add(int x){
    for (int i = x;i < N;i += lowbit(i))
        tr[i]++;
}
//求身高为1到x的小朋友个数
int query(int x){
    int sum = 0;
    for (int i = x;i > 0;i -= lowbit(i)){
        sum += tr[i];
    }
    return sum;
}
int main (){
    scanf ("%d" , &n);
    for (int i = 1;i <= n;i++)  scanf ("%d" , &a[i]) , a[i]++; //树状数组中下标从1开

    //先求每个小朋友左边比他大的数的个数
    for (int i = 1;i <= n;i++){
        add(a[i]);  //原数组发生变化，要改变对应的树状数组节点
        cnt[i] += i - query(a[i]);  //左边大于a[i]的数的个数
    }

    memset(tr , 0 , sizeof tr);
    for (int i = n;i;i--){
        add(a[i]);
        cnt[i] += query(a[i] - 1);
    }
    //有了cnt数组，然后求不满意度
    //如果一个小朋友他要移动cnt[i]次
    //那么他的不满意度应该等于 1 + 2 + 3 + 4 + ····+ n
    //等差数列求和
    //cnt[i]就是有cnt[i]项
    //所以求和公式为s = (a1 + an) * cnt[i] / 2
    //a1 = 1 an = a1 + (n-1)d = n
    //s = (1+cnt[i])*cnt[i] / 2
    long long res = 0;
    for (int i = 1;i <= n;i++){
        res += (1LL + cnt[i]) * cnt[i] / 2;
    }
    cout << res << endl;
    return 0;
}