#include #include

using namespace std;

typedef vector Data;

int merge_and_count_inversions(const Data &A, const Data &B, Data &C) { int inversions = 0; int i = 0, j = 0; while (i < A.size() && j < B.size()) { if (A[i] <= B[j]) { C.push_back(A[i++]); } else { C.push_back(B[j++]); inversions += A.size() - i; // 统计此次合并导致的逆序对数量 } } while (i < A.size()) { C.push_back(A[i++]); } while (j < B.size()) { C.push_back(B[j++]); } return inversions; }

int count_inversions(const Data &A) { if (A.size() <= 1) return 0; Data B(A.begin() + A.size() / 2, A.end()); Data C; int inversions_left = count_inversions(A.substr(0, A.size() / 2)); int inversions_right = count_inversions(B); int inversions_merged = merge_and_count_inversions(A, B, C); return inversions_left + inversions_right + inversions_merged; }

int main() { Data data = {2, 3, 8, 6, 1}; cout << "数组有逆序对: " << count_inversions(data) << endl; return 0; }