#include <bits/stdc++.h> using namespace std; int main() { int n,a[10000],sum=0; cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; } for(int i=0;i<n;i++) for(int j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) sum++;swap(a[j],a[j+1]); } cout<<sum; return 0; }模拟

• 计算逆序对个数的两种主要方法：归并排序和树状数组。

归并排序方法

• 归并排序：利用归并排序过程中的合并步骤来计算逆序对。在合并两个有序子数组时，若从右侧数组取出的元素比左侧数组的元素小，则左侧数组中剩余的所有元素都与该元素构成逆序对。
• 代码实现：在归并排序的合并过程中增加计数器，每当右侧数组元素小于左侧数组元素时，增加左侧数组剩余元素数量到计数器。12

树状数组方法

• 树状数组：通过构建树状数组来快速查询和更新逆序对数量。每个数组元素对应树状数组中的一个节点，通过树状数组可以快速计算出小于当前元素的元素数量，从而得到逆序对数量。
• 算法复杂度：树状数组方法的时间复杂度为O(nlogn)，适用于处理大数据量的情况。6

暴力方法

• 暴力求解：通过双层循环直接比较数组中每对元素，计算逆序对数量。时间复杂度为O(n^2)，适用于小规模数据。
• 代码示例：

for(int i = 0; i < n; i++)
    for(int j = 0; j < n - i - 1; j++)
        if(a[j] > a[j+1]){
            sum++;
            swap(a[j], a[j+1]);
        }

• 适用场景：当数据量较小，对时间复杂度要求不高时，可以使用暴力方法。5