#include <iostream>#include <algorithm>#include <vector>using namespace std;/* * 題目最終歸結(jié)到求每個數(shù)的逆序?qū)Φ膫€數(shù)，逆序?qū)Φ膫€數(shù)有多少個該數(shù)就要交換多少次 * 方法：歸并求逆序?qū)Φ膫€數(shù)，求出每個數(shù)的逆序?qū)Φ膫€數(shù)num * 步驟：先求小區(qū)間中的每個數(shù)的num,再回溯合并兩個小區(qū)間為一個大區(qū)間并更新大區(qū)間中每個數(shù)的num*/struct Node{ long long int value, num;//num為與value相關(guān)的逆序?qū)Φ膫€數(shù)總和（value前面比它大的數(shù)的個數(shù)+value后面比它小的數(shù)的個數(shù)）};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) { //將數(shù)合并到temp中之前計(jì)算這個數(shù)的逆序?qū)Φ膫€數(shù)（更新） 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]，個數(shù)為j-mid-1個 else a[j].num += mid - i + 1, temp[k++] = a[j++];//[ a[i]，a[mid] ]都大于a[j]，個數(shù)為mid-i+1個 } while (i <= mid) a[i].num += e - mid, temp[k++] = a[i++];//前半部分有剩余時，說明它比后半部分所有數(shù)都大，逆序?qū)Φ膫€數(shù)增加，且都增加e-mid個 for (i = s; i < k; i++)//寫回原容器，為下次更新準(zhǔn)備 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 ans = 0; for (int i = 0; i < n; i++) ans += a[i].num*(a[i].num+1)/2; cout << ans << endl; } return 0;}
