给你一组数据,让你求它的逆序数,我们可以先将这么数从小到大排序,然后一个一个插入到树状数组中去,c[i]表示第i个数前面有多少个数比它小,它的逆序就是i-Sum(a[i])。
代码如下:
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <math.h> #define M 500005 #define LL long long using namespace std; int a[M],c[M]; struct Data { int num; int dy; bool operator < (const Data h) const { return num<h.num; } }; struct Data data[M]; int Lowbit(int x) { return x & (-x); } void Insert(int x,int d) { while(x<=M) { c[x]+=d; x+=Lowbit(x); } } int Sum(int x) { int sum=0; while(x>0) { sum+=c[x]; x-=Lowbit(x); } return sum; } int main() { int n; while(scanf("%d",&n),n) { memset(a,0,sizeof(a)); memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) { scanf("%d",&data[i].num); data[i].dy=i; } sort(data+1,data+1+n); int k=2; a[data[1].dy]=1; for(int i=2;i<=n;i++) { if(data[i].num!=data[i-1].num) { a[data[i].dy]=k; k++; } else a[data[i].dy]=k; } LL ans=0; for(int i=1;i<=n;i++) { Insert(a[i],1); ans+=(i-Sum(a[i])); } printf("%lld\n",ans); } return 0; }