题目链接：
POJ 2299 Ultra-QuickSort
/*************Segment Tree Solution**************/
//19700K 1282MS
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
using namespace std;
const int maxn=500050;int n;
long long data[maxn],tmp[maxn],ans;struct SegTree{int left,right,num;
}segtree[maxn<<2];inline void build(int left,int right,int cur)
{segtree[cur].left=left;segtree[cur].right=right;segtree[cur].num=0;if(left==right) return ;int mid=(left+right)>>1;build(left,mid,lson(cur));build(mid+1,right,rson(cur));
}inline void query(int a,int b,int cur)
{int left=segtree[cur].left;int right=segtree[cur].right;if(left==a&&right==b){ans+=segtree[cur].num;return;}int mid=(left+right)>>1;if(b<=mid) query(a,b,lson(cur));else if(a>mid) query(a,b,rson(cur));else{query(a,mid,lson(cur));query(mid+1,b,rson(cur));}
}inline void update(int pos,int cur)
{int left=segtree[cur].left;int right=segtree[cur].right;if(left==right){segtree[cur].num++;//有可能有相同的数字出现return;}int mid=(left+right)>>1;if(pos<=mid) update(pos,lson(cur));else update(pos,rson(cur));segtree[cur].num=segtree[lson(cur)].num+segtree[rson(cur)].num;
}int main()
{//freopen("poj2299in.txt","r",stdin);while(~scanf("%d",&n)&&n){ans=0;for(int i=0;i<n;i++){scanf("%lld",&data[i]);tmp[i]=data[i];}sort(tmp,tmp+n);int tot=unique(tmp,tmp+n)-tmp;build(0,tot-1,1);for(int i=0;i<n;i++){int id=lower_bound(tmp,tmp+tot,data[i])-tmp;query(id,tot-1,1);update(id,1);}printf("%lld\n",ans);}return 0;
}/***********MergeSort Solution***********/
//7360K 407MS
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=500050;int n;
long long ans,a[maxn],T[maxn];inline void MergeSort(long long* a,int low,int high,long long* T)
{if(low+1<high){int mid=(low+high)>>1;MergeSort(a,low,mid,T);MergeSort(a,mid,high,T);int p=low,q=mid,i=low;while(p<mid||q<high){if(q>=high||(p<mid&&a[p]<a[q])) T[i++]=a[p++];else {T[i++]=a[q++];ans+=(mid-p);}}for(int i=low;i<high;i++) a[i]=T[i];}}int main()
{freopen("poj2299in.txt","r",stdin);while(~scanf("%d",&n)&&n){ans=0;for(int i=0;i<n;i++){scanf("%lld",&a[i]);}MergeSort(a,0,n,T);printf("%lld\n",ans);/*for(int i=0;i<n;i++){printf("%d",a[i]);if(i<n-1) printf(" ");else printf("\n");}*/}return 0;
}/***********Binary Indexed Tree***************/
//9320K 813MS
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn=500050;int n,tot;
int bits[maxn];
long long data[maxn],tmp[maxn];inline void update(int pos)
{while(pos<=tot){bits[pos]++;pos+=(pos&(-pos));}
}inline int solve(int pos)
{int sum=0;while(pos>0){sum+=bits[pos];//bits[pos]存储从1--id中数字的个数pos-=(pos&(-pos));}return sum;
}int main()
{//freopen("poj2299in.txt","r",stdin);while(~scanf("%d",&n)&&n){for(int i=1;i<=n;i++){scanf("%lld",&data[i]);tmp[i]=data[i];}sort(tmp+1,tmp+n+1);tot=unique(tmp+1,tmp+1+n)-tmp;long long ans=0;memset(bits,0,sizeof(bits));/*for(int i=n;i>=1;i--){int id=lower_bound(tmp+1,tmp+tot,data[i])-tmp;ans+=solve(id); //solve(id)得到的是树状数组中比data[i]小的数字个数，//因为是倒着插入树状数组的，那么这个solve(id)就是data[i]的逆序数了update(id);}*///两种写法都可以for(int i=1;i<=n;i++){int id=lower_bound(tmp+1,tmp+tot,data[i])-tmp;ans+=(i-solve(id)-1);//正着插入的话，solve(id)就是1~i-1中比data[i]小的数字个数//一共是i-1个数(去掉data[i])，所以由data[i]引起的逆序对数是i-1-solve(id)update(id);}printf("%lld\n",ans);}return 0;
}