#include <iostream>#include <algorithm>#include <vector>using namespace std;/* * 归并求逆序数 * 方法一：求出每个数的逆序对的个数num，对所有num求和后除以2得到逆序数 * 步骤：先求小区间中的每个数的num,再回溯合并两个小区间为一个大区间并更新大区间中每个数的num */struct Node{ long long int value, num;//num为与value相关的逆序对的个数总和（value前面比它大的数的个数+value后面比它小的数的个数）};void Merge(vector<Node>&a, int s, int e, vector<Node>&temp){ int mid = (s + e) / 2; int i = s, j = mid + 1; int k = s;//k从哪儿开始无所谓，我们这儿从s开始 while (i <= mid&&j <= e) { //将数合并到temp中之前计算这个数的逆序对的个数（更新） if (a[i].value <= a[j].value) a[i].num += j - mid - 1, temp[k++] = a[i++];//[ a[mid+1]，a[j-1] ]都小于a[i]，个数为j-mid-1个 else a[j].num += mid - i + 1, temp[k++] = a[j++];//[ a[i]，a[mid] ]都大于a[j]，个数为mid-i+1个 } while (i <= mid) a[i].num += e - mid, temp[k++] = a[i++];//前半部分有剩余时，说明它比后半部分所有数都大，逆序对的个数增加，且都增加e-mid个 for (i = s; i < k; i++)//写回原容器，为下次更新准备 a[i] = temp[i];}/** 递归二分*/void MergeSort(vector<Node>&a, int s, int e, vector<Node>&temp){ if (s < e) { int mid = (s + e) / 2; MergeSort(a, s, mid, temp); MergeSort(a, mid + 1, e, temp); Merge(a, s, e, temp); }}int main(){ int n; while (cin >> n) { vector<Node>a(n); vector<Node>temp(n); for (int i = 0; i < n; i++) cin >> a[i].value, a[i].num = 0; MergeSort(a, 0, n - 1, temp); long long int sum = 0; for (int i = 0; i < n; i++) sum += a[i].num; cout << sum/2 << endl; } return 0;}#include <iostream>#include <algorithm>#include <vector>using namespace std;/* * 归并求逆序数 * 方法二：求出每个数前面比自己大的数的个数count，累加即为序列的逆序数 */long long int Merge(vector<int>&a, int s, int e, vector<int>&temp){ long long int count = 0; int mid = (s + e) / 2; int i = s, j = mid + 1; int k = s; while (i <= mid&&j <= e) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++],count+=j-k;//累加 } while (i <= mid) temp[k++] = a[i++]; for (i = s; i < k; i++) a[i] = temp[i]; return count;}/** 递归二分*/long long int MergeSort(vector<int>&a, int s, int e, vector<int>&temp){ long long int count = 0; if (s < e) { int mid = (s + e) / 2; count += MergeSort(a, s, mid, temp); count += MergeSort(a, mid + 1, e, temp); count += Merge(a, s, e, temp); } return count;}int main(){ int n; while (cin >> n) { vector<int>a(n); vector<int>temp(n); for (int i = 0; i < n; i++) cin >> a[i]; long long int ans = MergeSort(a, 0, n - 1, temp); cout << ans << endl; } return 0;}
