题意：
给一个n个整数组成的序列，每次只能交换相邻的两个元素，问你最少要进行多少次交换才能使得整个整数序列上升有序。
题解：
冒泡排序的交换次数等于数组中所有数的逆序数之和。逆序数可以用树状数组求出。具体操作：
构建范围为1-n的树状数组，每次出现一次，该位置就加1，所以对于每个j，树状数组得到的前n项和就是满足i<j,ai<=aj的i的个数。从而可以用总的可以减去上面的个数，便可以得到前面比ai大的个数。
然后考虑到，数组中元素范围比较大，数组中元素数目比较少。所以要离散化。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;const int maxn = 500000+1000;int c[maxn];
int lowbit(int x)
{return x & -x;
}int sum(int x)
{int res=0;while(x>0){res+=c[x];x-=lowbit(x);}return res;
}void add(int x,int v)
{while(x<maxn){c[x]+=v;x+=lowbit(x);}
}
struct node
{int v,index;bool operator < (const node& a)const{return v<a.v;}
}a[maxn];//原始
int b[maxn];//离散化后
int main()
{int n;while(cin>>n,n){for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].index = i;}sort(a+1,a+1+n);b[a[1].index]=1;for(int i=2;i<=n;i++)///离散化{if(a[i].v == a[i-1].v)b[a[i].index] = b[a[i-1].index ];elseb[a[i].index] = i;}memset(c,0,sizeof c);long long ans=0;for(int i=1;i<=n;i++){ans += i-1-sum(b[i]);///总的减去比它小的add(b[i],1);}cout<<ans<<endl;}
}