莫说啥 @ 2019-08-22 16:12:03
#include<iostream>
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
int nixu(int a[],int m,int l)
{
if(m==l)
return 0;
else if(l-m==1)
{
if(a[l]>=a[m])
return 0;
else return 1;
}
int mid=(m+l)/2;
vector<int> b;
vector<int> c;
for(int i=m;i<=mid;i++)
{
b.push_back(a[i]);
}
for(int i=mid+1;i<=l;i++)
{
c.push_back(a[i]);
}
sort(b.begin(),b.end());
sort(c.begin(),c.end());
int num=0;
int t1=b.size()-1,t2=c.size()-1;
while(t1>=0&&t2>=0)
{
if(b[t1]<=c[t2])
t2--;
else{
t1--;
num+=t2+1;
}
}
return num+nixu(a,m,mid)+nixu(a,mid+1,l);
}
int main()
{
int n,a[500005];
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
cout<<nixu(a,1,n)<<endl;
return 0;
}
by fzfnf @ 2019-08-22 16:24:27
@莫说啥 使用归并排序
by Computer1828 @ 2019-08-22 16:26:56
@莫说啥 推荐食用:归并排序求逆序对,值域线段树求逆序对,树状数组求逆序对(其实和线段树没啥区别)
by End_donkey @ 2019-08-22 16:27:46
树状数组
by caidzh @ 2019-08-22 20:16:08
你甚至还可以平衡树求逆序对