想直接转化为“正序对”求解但是不知道哪里出了问题)求调orz
#include <bits/stdc++.h>
using namespace std;
int n,a[300010],b[300010];
long long ans;
void ms(int l,int r)//mergesort归并排序
{
int mid=l+(r-l)/2;
if(l==r) return;//只剩一个数就返回
ms(l,mid); ms(mid+1,r);
int i=l,j=mid+1,k=0;//i左j右指针
//ai<aj才可以握手
while(i<=mid && j<=r)//同时填入左右
{
if(a[i]<a[j])
{
ans+=mid-i+1;//计算正序对(
b[++k]=a[i++]; //填入小的数
}
else b[++k]=a[j++];
}
while(i<=mid)//右边填完了就填左边
b[++k]=a[i++]; //无法左右比较,继续填下去!
while(j<=r)//左边填完了就填右边
b[++k]=a[j++];
for(int i=l;i<=r;i++) a[i]=b[i]; //a赋值为排序后
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
ms(1,n);
//寻找正序对
cout<<ans;
}