题目描述
逆序对的数量(用归并排序)
逆序对:第一个数字大于第二个数字
样例
LL merge_sort(int q[],int l,int r)
{
if(l>=r) return 0;
//先计算左右两边逆序对的数量
int mid=(l+r)>>1;
LL res=merge_sort(q,l,mid)+merge_sort(q,mid+1,r);
//开始计算两边逆序对的数量
int i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<q[j])a[k++]=q[i++];
//左边大于右边时
else
{
a[k++]=q[j++];
//逆序对的数量就是左边剩下的数的数量
res+=mid-i+1;
}
}
//处理一边存完后剩下一边的数
while(i<=mid)
a[k++]=q[i++];
while(j<=r)
a[k++]=q[j++];
//将排好序的数组再存回原数组中
for(i=l,j=0;i<=r;i++,j++)
a[k]=q[i];
return res;
}
LL merge_sort(int l,int r)
{
if(l>=r)return 0;
int mid=l+r>>1;
LL res=merge_sort(l,mid)+merge_sort(mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j])temp[k++]=q[i++];
else
{
temp[k++]=q[j++];
res+=mid-i+1;
}
}
while(i<=mid)temp[k++]=q[i++];
while(j<=r)temp[k++]=q[j++];
//i=l指明对应的是原数组,j=0指明对应的是临时的数组,故形参中可以没有int q[]
for(int i=l,j=0;i<=r;i++,j++)q[i]=temp[j];
return res;
}
你好,LL res=merge_sort(l,mid)+merge_sort(mid+1,r);是什么意思,加起来是什么