找r中的每一个点 是否小于l里的任意数 计算数量 求得si
如何快速求出s1~sm?
如果j小于i 则i之后所有的值都大于等于j 与j构成逆序对
而i之前的数都已经扫过了,没有停下来,说明都小于等于j 不构成逆序对
用res=mid-i+1
来表示
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int a[N],temp[N];
LL merge_sort(int a[],int l,int r){
if(l>=r) return 0;
int mid=l+r>>1;
LL res=merge_sort(a,l,mid)+merge_sort(a,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) temp[k++]=a[i++];
else {
res+=mid-i+1;
temp[k++]=a[j++];
}
}
while(i<=mid) temp[k++]=a[i++];
while(j<=r) temp[k++]=a[j++];
for(int i=l,k=0;i<=r;i++,k++) a[i]=temp[k];
return res;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<merge_sort(a,0,n-1)<<endl;
}
原来把LL res=0;放成全局变量就不用让res=两个递归的和了.....原来如此!!!!想了太久这句话的作用!!!每次看递归的代码都要举例把每层的情况在纸上列出来才能弄明白....真难啊!!
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=1e5+10;
typedef long long LL;
int a[N],temp[N];
LL res;
LL merge_sort(int a[],int l,int r){
if(l>=r) return 0;
int mid=l+r>>1;
merge_sort(a,l,mid);
merge_sort(a,mid+1,r);
int i=l,j=mid+1,k=0;
while(i<=mid&&j<=r){
if(a[i]<=a[j]) temp[k++]=a[i++];
else {
res+=mid-i+1;
temp[k++]=a[j++];//注意这两句不能调换顺序!!!
}
}
while(i<=mid) temp[k++]=a[i++];
while(j<=r) temp[k++]=a[j++];
for(int i=l,k=0;i<=r;i++,k++) a[i]=temp[k];
return res;
}
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<merge_sort(a,0,n-1)<<endl;
}