题意：求逆序数对数量。
思路一：暴力，O(N^2)，超时。
思路二：虽然Ai很大，但是n比较小，可以离散化，得到每个Ai排序后的位置Wi，然后按照输入的顺序，每个Ai对答案的贡献是Wi-Sum(Wi-1)-1.Sum(x)表示1-x中在之前出现的总数，也即非逆序数对的数量，再减去Ai本身，就是Ai的贡献。可以用树状数组或者线段树做。O(NlogN).表达能力有限，大家见谅，详细看代码。
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 typedef long long ll; 7 const int N=7e4; 8 int n,a[N],b[N]; 9 ll c[N]; 10 int lowbit(int x){ 11 return x&(-x); 12 } 13 void add(int i,int x) 14 { 15 while(i<=n) 16 { 17 c[i]+=x; 18 i+=lowbit(i); 19 } 20 } 21 ll Q(int i)//1到i的和 22 { 23 ll sum=0; 24 while(i) 25 { 26 sum+=c[i]; 27 i-=lowbit(i); 28 } 29 return sum; 30 } 31 int main() 32 { 33 while(scanf("%d",&n)!=EOF) 34 { 35 for(int i=1;i<=n;i++) 36 { 37 scanf("%d",&a[i]); 38 b[i]=a[i]; 39 } 40 sort(b+1,b+n+1); 41 for(int i=1;i<=n;i++) 42 a[i]=lower_bound(b+1,b+n+1,a[i])-b; 43 ll ans=0; 44 for(int i=1;i<=n;i++) 45 { 46 add(a[i],1); 47 ans+=a[i]-Q(a[i]-1)-1; 48 } 49 printf("%I64d ",ans); 50 } 51 return 0; 52 }
思路三：归并排序，这个很好懂
合并的时候，如果左边的数比右边的小，就不是逆序，如果大了，说明是逆序了，并且从这个位置往后倒中线的都是比右边当前这个数大，所以答案加上m-i+1。代码是测试的，没有去交。
#include<stdio.h> #include<string.h> const int N=1111; int a[N],b[N]; int ans; void merge(int l,int m,int r){ int i=l; int j=m+1; int k=l; while(i<=m&&j<=r){ if(a[i]>a[j]){ b[k++]=a[j++]; ans+=m-i+1; }else{ b[k++]=a[i++]; } } while(i<=m) b[k++]=a[i++]; while(j<=r) b[k++]=a[j++]; for(i=l;i<=r;i++) a[i]=b[i]; } void merge_sort(int l,int r){ if(l<r){ int m=(l+r)>>1; merge_sort(l,m); merge_sort(m+1,r); merge(l,m,r); } } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); merge_sort(1,n); for(int i=1;i<=n;i++) printf("%d ",a[i]); printf(" %d ",ans); return 0; }
参考文章：http://www.bubuko.com/infodetail-637617.html
《ACM国际大学生程序设计竞赛题目与解读》P35