我好咸鱼。
归并排序之前写过,树状数组就是维护从后往前插入,找比现在插入的数大的数的数量。
如果值域大,可以离散化
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=100005;
int a[N],c[N],cnt,t[N],n,ans;
void modify(int x) {
for(int i=x; i<=n; i+=i&-i)
t[i]++;
}
int ask(int x) {
int res=0;
for(int i=x; i; i-=i&-i)
res+=t[i];
return res;
}
int main() {
scanf("%d",&n);
for(int i=1; i<=n; i++) scanf("%d",&a[i]),c[i]=a[i];
sort(c+1,c+1+n);
int u=unique(c+1,c+1+n)-c-1;
for(int i=n; i>=1; i--) {
a[i]=lower_bound(c+1,c+1+u,a[i])-c;
ans+=ask(a[i]);modify(a[i]);
}
printf("%d",ans);
}
归并排序求
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,a[50005],b[50005];
int merge(int l,int r) {
int ans=0;
if(l>=r) return 0;
int mid=l+r>>1;
ans+=merge(l,mid),ans+=merge(mid+1,r);
int i=l,j=mid+1,k=0,cnt=0;
while(i<=mid&&j<=r) {
if(a[i]<=a[j]) b[k++]=a[i++];
else cnt+=mid-i+1,b[k++]=a[j++];
}
while(j<=r) b[k++]=a[j++];
while(i<=mid) b[k++]=a[i++];
for(k=0;k<r-l+1;k++) {
a[l+k]=b[k];
}
return cnt+ans;
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
cout<<merge(1,n);
}