归并排序

思路

使用h保存身高，m保存移动次数，idx保存上一位置，

移动次数可以在每轮比较结束，更新原数组时计算前后位置偏移量得出。

不高兴程度 = 1 + 2 + 3 + … + 移动次数(高斯公式)

代码

#include <iostream>
#include <cmath>
using namespace std;

const int N = 100010;
typedef long long LL;

int n;

struct
{
    int h;  // 身高
    int idx;  // 上一次位置
    LL m;  // 移动长度
} q[N], tmp[N];

void merge_sort(int l, int r)
{
    if(l >= r)
        return;

    int mid = (l + r) >> 1;

    merge_sort(l, mid), merge_sort(mid + 1, r);

    int k = l, i = l, j = mid + 1;
    while(i <= mid && j <= r)
        if(q[i].h <= q[j].h)
            tmp[k++] = q[i++];
        else
            tmp[k++] = q[j++];

    while(i <= mid)
        tmp[k++] = q[i++];
    while(j <= r)
        tmp[k++] = q[j++];

    // 更新上一位置idx
    // 将|本次移动长度|累加到总长度
    for(i = l; i < k; i++)
        q[i] = { tmp[i].h, i, tmp[i].m + abs(tmp[i].idx - i) };

}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
        scanf("%d", &q[i].h), q[i].idx = i;

    merge_sort(1, n);

    LL cnt = 0;

    for(int i = 1; i <= n; i++)
        cnt += (q[i].m + 1) * q[i].m / 2;

    printf("%lld\n", cnt);
}

心得体会：

第一天写的时候发现输出不对，改了好几次还不行，就弃坑了，

第二天认真看了下大佬写的树状数组题解，才发现我弄错不高兴程度的计算方法，

在懵圈中改了下计算公式，意外的过了6个点，

不过看了半天没想到为啥wa了，就先写题解了，

写完又瞄了眼wa的输出，总感觉是爆int了，把m的类型改成long long，然后就AC了。
(用int，然后计算前(LL)也是可以的）

真是「懵⚪树上懵逼果，懵⚪树下只有我.jpg」

应该可以写的简单点，不过脑子混乱的不行了
（毕竟是一天前写的代码，能稍稍看懂已经是万幸了 ○|￣|_

暴力和树状数组的做法参考 https://www.acwing.com/solution/content/7296/