#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; struct node { int num; int pos; }; node st[500010]; int reflect[500010]; int a[500010]; int n; bool cmp(node a,node b) { return a.num<b.num; } int lowbit(int x) { return x&(-x); } int sum(int x) { int ret=0; while(x>0) { ret+=a[x]; x-=lowbit(x); } return ret; } void add(int x,int d) { while(x<=n) { a[x]+=d; x+=lowbit(x); } } int main() { while(scanf("%d",&n)!=EOF) { if(!n) break; memset(a,0,sizeof(a)); for(int i=0;i<n;i++) { scanf("%d",&st[i].num); st[i].pos=i; } sort(st,st+n,cmp); for(int i=0;i<n;i++) { reflect[st[i].pos]=i+1; } long long ans=0; for(int i=0;i<n;i++) { int tem=sum(reflect[i]); ans+=i-tem; add(reflect[i],1); } cout<<ans<<endl; } return 0; }
poj_2299Ultra-QuickSort,树状数组离散化
求逆序数