题目链接：
?id=2299
题目大意：
给你一个包含N个整数的序列，只能通过交换相邻的数字，最终变为升序顺序，，问：最少需要多少次交换。
思路：
其实就是问冒泡排序的交换次数。其实就是求原序列的逆序数。用归并排序、线段树、树状数组都可以做。
但是如果用线段树和树状数组来做的话，因为元素个数是500000，但是元素值范围却是999999999，需
要先离散化。这里用间接排序的方法。用一个数组Arr[]存放原序列的值，另一个数组Id[]存放原序列编号
树状数组来求逆序数。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define LL __int64using namespace std;int Tree[500050],Arr[500050],Id[500050],N = 500050;int cmp(const int x,const int y){return Arr[x] < Arr[y];}int Lowbit(int i){return i & (-i);}void Update(int i,int x){while(i <= N){Tree[i] = Tree[i] + x;i += Lowbit(i);}}LL Query(int n){LL sum = 0;while(n > 0){sum += Tree[n];n -= Lowbit(n);}return sum;}int main(){int N;while(cin >> N && N){memset(Tree,0,sizeof(Tree));for(int i = 1; i <= N; ++i){cin >> Arr[i];Id[i] = i;}sort(Id+1,Id+N+1,cmp); //间接排序，得到编号//for(int i = 1; i <= N; ++i)//cout << Arr[i] << ' ' << Id[i] << endl;LL ans = 0;for(int i = 1; i <= N; ++i) //求逆序数{Update(Id[i],1);ans += i – Query(Id[i]);}cout << ans << endl;}return 0;}
深重如溺入蓝色的海洋，无法呼吸。
