显然不能直接模拟冒泡排序，其实交换的次数就是序列的逆序对数。
由于数据范围是0 ≤ a[i] ≤ 999,999,999所以先要离散化，，然后用合适的数据结果求出逆序
可以用线段树一步一步添加a[i]，每添加前查询前面添加比它的大的有多少个就可以了。
也可用树状数组，由于树状数组求的是(1…x)的数量和所以每次添加前查询i-sum（a[i]）即可
树状数组：
//5620K688MS#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;#define ll long long#define lowbit(x) (x&-x)const int M=5e5+100;int num[M];int Hash[M];int tree[M]; //树状数组int n;int Bin(int val) //二分出离散后的序号{int l=0,r=n-1;while(r>=l){int m=(l+r)>>1;if(Hash[m]==val) return m+1;if(Hash[m]>val) r = m-1;else l=m+1;}}void add(int rt,int x){while(rt<=M-1){tree[rt]+=x;rt+=lowbit(rt);}}ll getsum(int rt){ll s=0;while(rt>0){s+=tree[rt];rt-=lowbit(rt);}return s;}int main(){while(scanf("%d",&n),n){memset(tree,0,sizeof(tree));ll ans=0;for(int i=0;i<n;i++){scanf("%d",&num[i]);Hash[i]=num[i];}sort(Hash,Hash+n);for(int i=0;i<n;i++){int val=Bin(num[i]);ans+=(ll)i-getsum(val);add(val,1);}printf("%I64d\n",ans);}return 0;}
用分治法求逆序数也可，分成两个数组B，C 。 B中的逆序数+C中的逆序数+对于每一个C[i]B中比它大的个数
所以可以借助归并排序实现顺带算出逆序数
//5428K625MS#include<cstdio>#include<algorithm>#include<iostream>#include<cstring>using namespace std;#define ll long long#define lowbit(x) (x&-x)const int M=5e5+100;int num[M];int tmp[M];int Hash[M];int n;int Bin(int val) //二分出离散化后的序号{int l=0,r=n-1;while(r>=l){int m=(l+r)>>1;if(Hash[m]==val) return m+1;if(Hash[m]>val) r = m-1;else l=m+1;}}ll merge_count(int l,int r){if(l==r){return 0;}ll cnt=0;int m=(l+r)>>1;cnt+=merge_count(l,m);cnt+=merge_count(m+1,r);int a=0,b=l,c=m+1;while(a<r-l+1){if(b<=m&& (c==r+1 ||num[b]<=num[c])){tmp[a++]=num[b++]; // sort}else{tmp[a++]=num[c++]; // sortcnt+=m-b+1;}}for(int i=0;i<r-l+1;i++) //还原到原数列num[l+i]=tmp[i];return cnt;}int main(){while(scanf("%d",&n),n){for(int i=0;i<n;i++){scanf("%d",&num[i]);Hash[i]=num[i];}sort(Hash,Hash+n);for(int i=n-1;i>=0;i–){int val=Bin(num[i]);num[i+1]=val;//我离散后的数列设成从1开始到n，因为后面分治怕出错就套用了线段树从结点1开始的写法…2333}printf("%I64d\n",merge_count(1,n));}return 0;}
纵然伤心，也不要愁眉不展，因为你不知是谁会爱上你的笑容
