题目链接：https://vjudge.net/problem/POJ-2299
推荐讲解树状数组的博客：https://blog.csdn.net/int64ago/article/details/7429868
题目意思就是让我们把无序的一些数字经过相邻数字间两两交换，最后变成不递减的数字。我们要求出最少要交换的次数。
逆序对（百度的）：对于一个包含N个非负整数的数组，A[1..n]，A[1..n]，如果有i < j，且A[ i ]>A[ j ]，则称(A[ i] ,A[ j] )为数组A中的一个逆序对。
了解了一下树状数组就过来做这题了，一开始用map容器，一直TLE，后面看了论坛，发现不用map容器编号就可以过，并且还可以用归并排序来写，这两种方法都可以用来求逆序对数量。
树状数组：
因为数字最大可以达到999999999，我们用数组是存不下来的，所以我们要给每一个数字编号，
假设现在就是 9 1 0 5 4
那么我给它们编一个号码就是 1 2 3 4 5 状态一
我们要把它们用两两交换的方法来进行排序，排序之后就是 0 1 4 5 9
对应的编号就是 3 2 5 4 1 状态二
那现在问题就可以看成我们把编号1到5从状态一用相邻数字交换点的方法变换到状态二，它等同于从状态二变换到状态一，我们现在就讨论从状态二变换到状态一需要的步数就可以了，那么我们看状态二，从左到右枚举每一个数字，每次加上它前面比他大的数字的数量（就相当于把他交换到所有比他大的数字前面），这个用树状数组里面求区间和的操作就可以了，假设现在编号是k，那么加的数量就是函数sum（n）-sum（k）。恩，没了。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 500005
struct node{
int index,value;//编号和一开始的值
}a[maxn];
LL b[maxn],ans;//要用long long
int n;
bool cmp(node s1,node s2){
return s1.value<s2.value;
}
int lowbit(int x){
return x&(-x);
}
LL sum(int x){
LL ans=;
while(x>){
ans+=b[x];
x-=lowbit(x);
}
return ans;
}
void add(int x){
while(x<maxn){
b[x]++;
x+=lowbit(x);
}
}
int main()
{
while(scanf("%d",&n)&&n){
ans=;
memset(b,,sizeof(b));
for(int i=;i<=n;i++){//编号我们从1开始，防止后面单点修改的时候死循环
scanf("%d",&a[i].value);
a[i].index=i;
}
sort(a+,a+n+,cmp);
for(int i=;i<=n;i++){
ans+=sum(n)-sum(a[i].index);
add(a[i].index);
}
printf("%lld\n",ans);
}
return ;
}
归并排序：
用归并排序也写了一下，复习了一下归并排序，开森。
归并排序用了二分的思想，先把一个大区间不断划分成两个小区间，知道不能划分，然后回溯的时候进行区间合并，在我们合并的时候就可以顺带求出逆序对的数量了，额，如果不会归并排序可以百度一下下。我们看下面的一个例子：
假设现在有了两个较小的排好了序的区间分别是2 6 9和 3 5 10。根据归并排序的原理，事实上他们在整个数组上面是连续的，就是
2 6 9 3 5 10这样排的，现在我们要和并他们，那么首先我们把两个区间里面最小的数字拿出来比较一下，2<3，那么2在第一个位置，然后6和3比较，6>3，那么我们要把3放在6的前面，那么我们要把3移几位呢，在连续的2 6 9 3 5 10 里面我们把3移到6前面是要经过6和9的，那么就是要移两位，那么这六个数字就变成了2 3 6 9 5 10，同理，接下来6>5，我们还是要把5移到6前面，那么还是2步，最后我们总结出一个规律，就是左边区间的a[i]和右边区间的a[j]相比较 ，如果a[i]<=a[j]，那么它们本来就是从小到大的，我们不移，如果是a[i]>a[j]那么我们需要移的数目就是mid-i+1，事实上面就是左边区间剩余数字的数目。
代码：
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<vector>
#include<set>
#include<cstdio>
#include<string>
#include<deque>
using namespace std;
typedef long long LL;
#define eps 1e-8
#define INF 0x3f3f3f3f
#define maxn 500005
LL ans,a[maxn],b[maxn],n;
void marge(int left,int mid,int right){
int l=left;
int r=mid+;
int cnt=l;
while(l<=mid&&r<=right){
if(a[l]<=a[r])
b[cnt++]=a[l++];
else{
b[cnt++]=a[r++];
ans+=mid-l+;//在这里加一下就可以了
}
}
while(l<=mid) b[cnt++]=a[l++];
while(r<=right) b[cnt++]=a[r++];
for(int i=left;i<=right;i++)
a[i]=b[i];
}
void marge_sort(int l,int r){
if(l==r){
return;
}
int mid=(l+r)/;
marge_sort(l,mid);
marge_sort(mid+,r);
marge(l,mid,r);
}
int main()
{
while(scanf("%lld",&n)&&n){
ans=;
for(int i=;i<n;i++){
scanf("%lld",&a[i]);
}
marge_sort(,n-);
printf("%lld\n",ans);
}
return ;
}