首先通过题目看看如何考察逆序数，什么是逆序数？逆序数就是找前面有几个比自己大的数
即如果i<j&&a[i]>a[j] 则a[i]和a[j]构成一个逆序对
这里排序求交换次数比正好就是我们前面讲到的逆序对吗？
因此我们首先就想到了o(logn)方法的归并排序 mergesort(int l,int r)
归并排序的思路就是：先二分分到不能再分,保证(l<r)，再将两个有序的序列合并起来。
如一个序列a[7]={100,29,8,9,10,5} 对齐归并排序步骤如下：
100,29,8,9,10,5
{100,29,8} {9,10,5}
{100} {29,8} {9,10} {5}
合并：
{100}{8,29},{9,10}{5}
{8,29,100},{5,9,10}
{5,8,9,10,29,100}
我们发现当和并的时候如果左边的a[p]>a[q],则产生了逆序，p-mid这一段的数都对a[q]构成逆序，因为他们是从小到大有序的了。
因此ans+=mid-p+1就是逆序对数
写出代码：
#include<iostream>
using namespace std;
int a[6]={100,29,8,9,10,5},b[6];
int ans=0;
void merge(int l,int mid,int r){
cout<<l<<" "<<mid<<" "<<r<<" "<<endl;
int p=l,q=mid+1,i=l;
while(p<=mid&&q<=r){//左右两部分都不要为空
//从左半数组复制到辅助数组
if(a[p]<=a[q]){
b[i++]=a[p++];
}else{ //从右半数组复制到辅助数组
b[i++]=a[q++];
ans+=mid-p+1;
}
}
//处理剩下的，一部分变为空了
while(p<=mid){
b[i++]=a[p++];
}
while(q<=r){
b[i++]=a[q++];
}
//写会原来的数组
for(int j=l;j<=r;j++){
a[j]=b[j];
}
}
void mergesort(int l ,int r){
if(r-l>0){
int mid=(l+r)/2;
int p=l,q=mid+1,i=l; //p为左边的第一个，q为右边的第一个
mergesort(l,mid);
mergesort(mid+1,r);
merge(l,mid,r);
}
}
int main(){
mergesort(0,5);
cout<<ans;
return 0;
}
//100,29,8,9,10,5
//0-2 3-5 {100,29,8} {9,10,5}
//0-1 3-4 {100,29} 8 {9,10} 5
//下面来看看树状数组，树状数组用于求解a[1]-a[i]区间和及单点修改问题。
#include<iostream>
using namespace std;
int n,a[10010],c[10010];
int lowbit(int x)
{
return x&(-x);
}
//C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]
//单点修改更新了a[i] 要更新对应的c[xxx]，其中c[xxx]包含a[i]
int update(int i,int k){
while(i<=n){
c[i]+=k;
i+==lowbit(i);
}
}
//求1到i的区间和a[1]+...+a[i]
//c[x1]+c[x2]+..+c[xx] xx=i...i-lowbit[i]..1
int getsum(int i){
int sum=0;
while(i>0){
sum+=c[i];
i-=lowbit(i);
}
return sum;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
update(i,a[i]);//输入等于单点修改值
}
return 0;
}如何用树状数组求解逆序数呢？
对于序列t 100,29,8,9,10,5
1 2 3 4 5 6
a[100]=1 a[29]=1 a[8]=1 a[9]=1 a[10]=1 a[5]=1
即update(100,1)，update(29,1),update(8,1)......
然后
getsum(100)为a[1]+...+a[100] t[1]前面小于t[1]的个数 i-getsum(100) 就是第i个数前面大于t[i]的个数
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1e5+5;
const int mod=99999997;
int n,c[N],temp[N],t[N];
long long ans=0;
struct node
{
int w;
int id;
}a[N],b[N];
int R()
{
int f=0;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c<='9'&&c>='0';c=getchar())
f=(f<<3)+(f<<1)+c-'0';
return f;
}
bool comp(node x,node y)
{
return x.w<y.w;
}
inline void merge(int x,int mid,int y)
{
int i=x,j=mid+1,head=x;
while(i<=mid&&j<=y)
{
if(c[i]<=c[j])
temp[head++]=c[i++];
else
{
ans=(ans+mid-i+1)%mod;
temp[head++]=c[j++];
}
}
while(i<=mid) temp[head++]=c[i++];
while(j<=y) temp[head++]=c[j++];
for(i=x;i<=y;i++)
c[i]=temp[i];
}
inline void mergesort(int a,int b)
{
if(a==b) return;
int mid=(a+b)/2;
mergesort(a,mid);
mergesort(mid+1,b);
merge(a,mid,b);
}
int lowbit(int x){
return x&(-x);
}
void update(int i,int k){
while(i<=n){
t[i]+=k;
i+=lowbit(i);
}
}
int getsum(int i){
int sum=0;
while(i>0){
sum+=t[i];
i-=lowbit(i);
}
return sum;
}
int main()
{
//freopen("a.in","r",stdin);
n=R();
for(int i=1;i<=n;i++)
{
a[i].w=R();
a[i].id=i;
}
for(int i=1;i<=n;i++)
{
b[i].w=R();
b[i].id=i;
}
sort(a+1,a+n+1,comp);
sort(b+1,b+n+1,comp);
for(int i=1;i<=n;i++)
c[b[i].id]=a[i].id;
for(int i=1;i<=n;i++){
update(c[i],1);
ans=(ans+i-getsum(c[i]))%mod;
}
cout<<ans<<endl;
return 0;
}参考资料：树状数组概念 https://www.cnblogs.com/xenny/p/9739600.html
归并排序求逆序数 https://blog.csdn.net/qq_41550842/article/details/81215935
树状数组求逆序数 https://blog.csdn.net/m0_38033475/article/details/80330157
有话要说...