7-8 逆序对 (10 分)
求逆序对。
输入格式:
第一行是一个整数n，（n<=1000,000）表示输入序列的长度，接下来一行是n个整数(每个数的绝对值小于)。
输出格式:
一个数，表示逆序对个数(逆序即任意一对数前面的数比后面的数大即为一对逆序对)。
输入样例:
在这里给出一组输入。例如：
10 1 3 5 7 9 8 4 2 6 10
输出样例:
在这里给出相应的输出。例如：
14
说明：样例中如1和3不是逆序对，而3和2是1对逆序对，例子中共有14对逆序对。题目中可能有某些数字出现多次的情况。
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<bits/stdc++.h>
using namespace std;
int a[1000002],b[1000002];
long long cnt=0;
void merge(int l,int r){
int m,k,k1,k2,t;
m=(l+r)/2;
k1=l;
k2=m+1;
k=l;
while(k1<=m&&k2<=r){
if(a[k1]<=a[k2]){
b[k]=a[k1];
k++;
k1++;
}
else{
b[k]=a[k2];
k++;
k2++;
cnt=cnt+m-k1+1;
}
}
while(k1<=m){
b[k]=a[k1];
k++;
k1++;
}
while(k2<=r){
b[k]=a[k2];
k++;
k2++;
}
for(t=l;t<=r;t++){
a[t]=b[t];
}
}
void mergesort(int l,int r){
if(l<r){
int m;
m=(l+r)/2;
mergesort(l,m);
mergesort(m+1,r);
merge(l,r);
}
}
int main(){
int n,i;
cin>>n;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
mergesort(1,n);
printf("%lld",cnt);
return 0;
}