---

一眼应该能看出来这道题朴素算法是冒泡排序，但是逆序对这类题要求复杂度小于等于O（nlogn）， 因此可以用线段树，树状数组，归并排序之类的试试。

洛谷上有一样的题：逆序对 - 洛谷

AC代码（归并排序）

#include <bits/stdc++.h>
using namespace std;int n,a[100001],b[100001];
long long ans;void merge(int l,int r){if(l==r)return;int mid=l+r>>1;merge(l,mid);merge(mid+1,r);//[l,i,mid][mid+1,j,r]int i=l,j=mid+1,k=l;while(i<=mid and j<=r){if(a[i]<a[j])b[k++]=a[i++];else b[k++]=a[j++],ans+=mid-i+1;//放入a[j],说明a[i,mid]都比a[j]大,产生mid-i+1个逆序对}while(i<=mid)b[k++]=a[i++];while(j<=r)b[k++]=a[j++];for(i=l;i<=r;++i)a[i]=b[i];
}int main(){ios::sync_with_stdio(false);cin.tie(nullptr),cout.tie(nullptr);cin>>n;for(int i=1;i<=n;++i)cin>>a[i];merge(1,n);cout<<ans;return 0;
}