【题目描述】
给定一个序列a1,a2,…,ana1,a2,…,an，如果存在i<ji<j并且ai>ajai>aj，那么我们称之为逆序对，求逆序对的数目。
【输入】
第一行为nn,表示序列长度，接下来的nn行，第i+1i+1行表示序列中的第ii个数。
【输出】
所有逆序对总数。
【输入样例】
4
3
2
3
2
【输出样例】
3
【提示】
N≤105，Ai≤105N≤105，Ai≤105。
#include <iostream>
using namespace std;
int a[999999],b[999999];
long long cnt;
void msort(int s,int t){
if(s==t) return;
int mid=(s+t)/2,i=s,j=mid+1,k=s;
msort(s,mid);
msort(mid+1,t);
while(i<=mid &&j<=t){
if(a[i]<=a[j])
b[k++]=a[i++];
else {
b[k++]=a[j++];
cnt+=mid-i+1;
}
}
while(i<=mid)
b[k++]=a[i++];
while(j<=t)
b[k++]=a[j++];
for(int i=s;i<=t;i++) a[i]=b[i];
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
msort(0,n-1);
cout<<cnt;
return 0;
}
因篇幅问题不能全部显示，请点此查看更多更全内容