题目链接：·【蓝桥】·小朋友排队

问题描述
　　n 个小朋友站成一排。现在要把他们按身高从低到高的顺序排列，但是每次只能交换位置相邻的两个小朋友。
　　每个小朋友都有一个不高兴的程度。开始的时候，所有小朋友的不高兴程度都是0。
　　如果某个小朋友第一次被要求交换，则他的不高兴程度增加1，如果第二次要求他交换，则他的不高兴程度增加2（即不高兴程度为3），依次类推。当要求某个小朋友第k次交换时，他的不高兴程度增加k。
　　请问，要让所有小朋友按从低到高排队，他们的不高兴程度之和最小是多少。
　　如果有两个小朋友身高一样，则他们谁站在谁前面是没有关系的。
输入格式
　　输入的第一行包含一个整数n，表示小朋友的个数。
　　第二行包含 n 个整数 H1 H2 … Hn，分别表示每个小朋友的身高。
输出格式
　　输出一行，包含一个整数，表示小朋友的不高兴程度和的最小值。
样例输入
3
3 2 1
样例输出
9
样例说明
　　首先交换身高为3和2的小朋友，再交换身高为3和1的小朋友，再交换身高为2和1的小朋友，每个小朋友的不高兴程度都是3，总和为9。
————————————————————————————————————
参考我的另一篇博客：
稍有不同的是，这里求的是逆序对，一组逆序记录两次（既要记录a[i].val后面比它小的组数，还要记录前面比它大的组数）
如对于 2 4 3 1 各组逆序对结果：
1 2 1 0
0 0 1 3
累加后为 1 2 2 3
然后各组 前n项和公式累加得到最终结果

解题思路

#include <iostream>

using namespace std;
typedef long long ll;
const int maxn = 100005;
struct note{
	int val;
	int num;
}; 
struct note a[maxn], b[maxn];
int n;
void merge(int l, int mid, int r){
	int i = l, j = mid + 1;
	int k = l;
	while(i<=mid && j<=r){
		if(a[i].val <= a[j].val){
			b[k++] = a[i++];
			b[k-1].num += (j-mid-1);
			//a[i].val后面比它小的有多少 
		}else{
			b[k++] = a[j++];
			b[k-1].num += (mid-i+1);
			//a[j].val前面比它大的有多少 
		}
	} 
	while(i<=mid){
		b[k++] = a[i++];
		b[k-1].num += (r-mid);
		//a[i].val后面比它小的有多少 
	}
	while(j<=r){
		b[k++] = a[j++]; 
		//b[k-1].num += (mid-i+1);
		//a[j].val前面比它大的有多少 
	}
	for(k = l; k <= r; ++k)
		a[k] = b[k];
}
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);
	merge(l, mid, r);
}
int main(){
	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> a[i].val;
	}
	Merge_sort(0, n-1);
	ll ans = 0;
	for(int i = 0; i < n; ++i)
		ans += (ll)(a[i].num+1)*a[i].num/ 2;
	cout << ans <<endl;
	return 0;
}