题目描述 Description
hzwer在研究逆序对。
对于数列{a}，如果有序数对(I,j)满足：i<j,a[i]>a[j]，则(i,j)是一对逆序对。
给定一个数列{a}，求逆序对个数。
输入数据较大，请使用scanf代替cin读入。
*为防卡评测，时限调低至1s
输入描述 Input Description
第一行一个数n,表示{a}有n个元素。
接下来n个数，描述{a}。
输出描述 Output Description
一个数，表示逆序对个数。
样例输入 Sample Input
5
3 1 5 2 4
样例输出 Sample Output
4
数据范围及提示 Data Size & Hint
对于10%数据，1<=n<=100.
对于20%数据，1<=n<=10000.
对于30%数据，1<=n<=100000.
对于100%数据，1<=n<=1000000,1<=a[i]<=10^8.
tips:我没有想故意卡你们时限。一点这样的意思都没有。你们不要听风就是雨……
题解；归并排序求逆序对。
#include<iostream>
using namespace std;
int a[],b[];
long long ans;
void msort(int l,int r)
{
if (l>=r) return;
int mid=(l+r)/;
msort(l,mid);
msort(mid+,r);
int i=l,j=mid+,t=l-;
while(i<=mid&&j<=r)//小为先，指针进。
{
if(a[i]<=a[j]) b[++t]=a[i++];
else
{
ans+=mid-i+;
b[++t]=a[j++];
}
}
while (i<=mid) b[++t]=a[i++];//大为后，直接补。
while (j<=r) b[++t]=a[j++];
for (i=l;i<=r;i++) a[i]=b[i];
return;
}
int main()
{
int n,m,i,j,k;
cin>>n;
for(i=;i<=n;i++) cin>>a[i];
msort(,n);
cout<<ans<<endl;
return ;
}
归并排序逆序对