思路:

$任给一个序列，只通过不断交换相邻的两个数使之有序，最小交换次数=逆序对个数k$
$依据贪心策略，冒泡排序每次交换相邻的一对数，会使得总的逆序对数量-1$
$(把他们两个数看作整体，对整体外的逆序对无影响，整体内逆序对由1\rightarrow0)$
$冒泡排序会执行k次使序列有序，即最小执行次数，故冒泡排序是该问题最优的排序方式$

$对于每一个数(小朋友的高度)而言，它与前面比它大的数构成k_1个逆序对，与后面比它小的数构成k_2个逆序对，$
$要把比它小的放它前面，比它大的数放在它后面，则至少进行k_1+k_2次交换，每次冒泡排序为1次交换$
$每个小朋友的不开心度=1+2+3+\cdots (k_1+k_2)=\dfrac{(k_1+k_2)(k_1+k_2+1)}{2}$
$故只需统计对于每个小朋友的高度在整个数组中构成的逆序对个数，即可算出该小朋友的不高兴度$

方法一:树状数组

$权值树状数组，树状数组对应的原数组存储的是每个数当前出现的次数$

【注意】

1.树状数组可以单独存在，对应的原数组可以是虚构的，但是其相关信息要能记录下来并转换到树状数组中存储，如此题中，h[i]存储的是原数据(第i个小朋友的高度)，原数组A[j]存储的是高度为j的小朋友的个数，树状数组tr[k]存储的是一段高度区间的小朋友个数，方便区间查询和单点更新

2.树状数组tr[k]存储的元素不会爆int，因为每个小朋友至多与其他n-1个小朋友构成逆序对，存储的数值不会超过n-1

3.每个小朋友的不高兴度可能会爆int，因为每个小朋友至多构成n-1个逆序对，不高兴度值为(n-1)(n-1+1)/2

4.树状数组的下标从1开始，而h[i]可能取0，要全部自增，使得tr[h[i]]的下标从1开始

5.求每个小朋友构成的逆序对个数，要分别求与前面更高的和后面更矮的构成的个数再求和，用到两次树状数组，tr[ ]存储的分别是对应两次遍历过程中，某段高度区间内已出现过的小朋友的个数，所以上一次操作后要进行数组清空，避免影响下一次操作结果

6.注意遍历的顺序：

前面更高=>从前往后遍历保证”前面”，使得每次查询到的，都是前面已出现的而不是后面更高的
后面更矮=>从后往前遍历保证”后面”，可以理解成前一种情况的翻转

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
typedef long long LL;
int n;
// h[i]记录第i个小朋友的高度
/*
tr[i]是所有小朋友可能的的高度([1~100001]:通过+1处理 使下标由1开始)对应的树状数组 
对应的原数组A[h[i]](虚构的)存储的是高度为h[i]的小朋友个数 
tr[i]可用来求一段区间的和(高度比原先h[i]小/大的小朋友数量)
*/
int h[N],tr[N];
// sum[i]记录每个小朋友 他前面比他矮的以及后面比他高的小朋友个数的总和(即小朋友自己的高度在整个数组中构成的逆序对个数)
int sum[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int a,int b)
{
    for(int i = a;i < N;i += lowbit(i))
        tr[i] += b;
}

int query(int a,int b)
{
    int s1 = 0,s2 = 0;
    for(int i = a - 1;i > 0;i -= lowbit(i))
        s1 += tr[i];
    for(int i = b;i > 0;i -= lowbit(i))
        s2 += tr[i];
    return s2 - s1;
}

int main()
{
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> h[i],h[i]++;  // +1 使得tr[h[i]]中高度下标从1开始

    // 求每个小朋友前面有多少个小朋友比他高
    for(int i = 1;i <= n;i ++)  // 从前往后
    {
        sum[i] = query(h[i] + 1,N - 1); // 查询的是已经记录的（即在当前小朋友之前出现过的）更高的小朋友的高度
        add(h[i],1);                    // 将这个高度记录下来(已出现)
    }

    // 清空 再求每个小朋友后面有多少个小朋友比他矮
    memset(tr,0,sizeof tr);
    for(int i = n;i > 0;i --)   // 从后往前
    {
        sum[i] += query(1,h[i] - 1); // 查询的是已经记录的（即在当前小朋友之后出现的）更矮的小朋友的高度
        add(h[i],1);                 // 将这个高度记录下来(已出现) 
    }

    LL res = 0; // 记录不高兴度总和
    for(int i = 1;i <= n;i ++) res += (LL)sum[i] * (sum[i] + 1) / 2;
    cout << res << endl;
    return 0;
}

方法二:归并排序过程中统计逆序对个数

采用两次归并排序，按从小到大和从大到小分别统计每个数前面比它大的数的个数和后面比它小的数的个数，即每个数构成的总逆序对数

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long int LL;
const int n = 1000010;
int N;          // 小朋友个数
int sum[n];     // sum[i]表示编号为i的小朋友在整个序列中构成的逆序对个数
LL res;         // 记录不高兴度总和

struct child
{
    int h;      // 小朋友高度
    int id;     // 小朋友编号
}c[n],tmp[n],backup[n]; // 原数组 归并排序用的辅助数组 备份数组

// 第一种归并(从小到大排序 顺便统计每个数与前面比它大的数构成的逆序对个数)
void merge1(int l,int mid,int r)
{
    int i = l,j = mid + 1,k = 1;
    while(i <= mid && j <= r)
        if(c[i].h > c[j].h) 
        {
            tmp[k++] = c[j++];
            sum[c[j - 1].id] += mid + 1 - i;
        }
        else tmp[k++] = c[i++];
    while(i <= mid) tmp[k++] = c[i++];
    while(j <= r) tmp[k++] = c[j++];
    i = l,k = 1;
    while(i <= r) c[i++] = tmp[k++];
}

void mergeSort1(int l,int r)
{
    if(l == r) return ;
    int mid = l + r >> 1;
    mergeSort1(l,mid);
    mergeSort1(mid + 1,r);
    merge1(l,mid,r);
}

// 第二种归并(从大到小排序 顺便统计每个数与后面比它小的数构成的逆序对个数)
void merge2(int l,int mid,int r)
{
    int i = l,j = mid + 1,k = 1;
    while(i <= mid && j <= r)
        if(c[i].h > c[j].h) 
        {
            tmp[k++] = c[i++];
            sum[c[i - 1].id] += r + 1 - j;
        }
        else tmp[k++] = c[j++];
    while(i <= mid) tmp[k++] = c[i++];
    while(j <= r) tmp[k++] = c[j++];
    i = l,k = 1;
    while(i <= r) c[i++] = tmp[k++];
}

void mergeSort2(int l,int r)
{
    if(l == r) return ;
    int mid = l + r >> 1;
    mergeSort2(l,mid);
    mergeSort2(mid + 1,r);
    merge2(l,mid,r);
}

int main()
{
    cin >> N;
    int H;
    for(int i = 1;i <= N;i++) cin >> H,c[i] = {H,i},backup[i] = {H,i};
    mergeSort1(1,N);
    for(int i = 1;i <= N;i++) 
        c[i] = backup[i];
    mergeSort2(1,N);
    for(int i = 1;i <= N;i++) res += (LL)sum[i] * (sum[i] + 1) / 2;
    cout << res << endl;
    return 0;
}