刚写了一发归并排序的逆序对（不会写二分的蒟蒻）
那就顺便复习一下树状数组求逆序对吧
来道裸题
题目:http://poj.org/problem?id=1804
题意:给定一个序列a[],每次只允许交换相邻两个数,最少要交换多少次才能把它变成非递降序列.
归并排序是将数列a[l,h]分成两半a[l,mid]和a[mid+1,h]分别进行归并排序，然后再将这两半合并起来。
在合并的过程中（设l<=i<=mid，mid+1<=j<=h），当a[i]<=a[j]时，并不产生逆序数；当a[i]>a[j]时，在前半部分中比a[i]大的数都比a[j]大，将a[j]放在a[i]前面的话，逆序数要加上mid+1-i。因此，可以在归并
排序中的合并过程中计算逆序数.
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int a[100001];
int ans;
void mergesort(int l,int r)
{int i,j,k,mid=(l+r)/2;if(l>=r) return;mergesort(l,mid);mergesort(mid+1,r);int *b=new int[r+1];for(i=l;i<=r;i++) b[i]=a[i];i=l,j=mid+1,k=l;while(i<=mid&&j<=r){if(b[i]<=b[j]) a[k++]=b[i++];else{a[k++]=b[j++];ans+=mid+1-i; }}while(i<=mid) a[k++]=b[i++];while(j<=r) a[k++]=b[j++];delete []b;
}
int main()
{int t,tt=0;scanf("%d",&t);while(t--){int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);mergesort(1,n);// for(int i=1;i<=n;i++) cout<<a[i]<<" ";printf("Scenario #%d:\n%d\n\n",++tt,ans);ans=0;}return 0;
}再来一道
poj2299
用树状数组求的话先离散化，然后再更新答案
开始不太好理解，可以手动强行模拟一波
假设输入的数组是9 1 0 5 4， 离散后的结果aa[ ] = {5,2,1,4,3};
在离散结果中间结果的基础上，那么其计算逆序数的过程是这么一个过程。
1，输入5， 调用upDate(5, 1),把第5位设置为1
1 2 3 4 5
0 0 0 0 1
计算1-5上比5小的数字存在么？ 这里用到了树状数组的getSum（5） = 1操作，
现在用输入的下标1 - getSum(5) = 0 就可以得到对于5的逆序数为0。
2. 输入2， 调用upDate(2, 1),把第2位设置为1
1 2 3 4 5
0 1 0 0 1
计算1-2上比2小的数字存在么？ 这里用到了树状数组的getSum（2） = 1操作，
现在用输入的下标2 - getSum(2) = 1 就可以得到对于2的逆序数为1。
3. 输入1， 调用upDate(1, 1),把第1位设置为1
1 2 3 4 5
1 1 0 0 1
计算1-1上比1小的数字存在么？ 这里用到了树状数组的getSum（1） = 1操作，
现在用输入的下标 3 - getSum(1) = 2 就可以得到对于1的逆序数为2。
4. 输入4， 调用upDate(4, 1),把第5位设置为1
1 2 3 4 5
1 1 0 1 1
计算1-4上比4小的数字存在么？ 这里用到了树状数组的getSum（4） = 3操作，
现在用输入的下标4 - getSum(4) = 1 就可以得到对于4的逆序数为1。
5. 输入3， 调用upDate(3, 1),把第3位设置为1
1 2 3 4 5
1 1 1 1 1
计算1-3上比3小的数字存在么？ 这里用到了树状数组的getSum（3） = 3操作，
现在用输入的下标5 - getSum(3) = 2 就可以得到对于3的逆序数为2。
6. 0+1+2+1+2 = 6 这就是最后的逆序数
分析一下时间复杂度，首先用到快速排序，时间复杂度为O(NlogN),
后面是循环插入每一个数字，每次插入一个数字，分别调用一次upData()和getSum()外循环N, upData()和getSum()时间O(logN) => 时间复杂度还是O(NlogN).
最后总的还是O(NlogN).
不得不说，手动模拟是个好东西O(∩_∩)O
http://poj.org/problem?id=2299
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500001;
int num[maxn],a[maxn],n;
struct node
{int val,pos;
}b[maxn];int s[maxn];
bool lisanhua(const node &a,const node &b)
{return a.val<b.val;
}int lowbit(int x)
{return x&(-x);
}
void add(int x)
{for(int i=x;i<=n;i+=lowbit(i))s[i]++;
}
int sum(int x)
{int ans=0;for(int i=x;i>0;i-=lowbit(i))ans+=s[i];return ans;
}
int main()
{long long ans=0;while((scanf("%d",&n))&&n){memset(s,0,sizeof(s));memset(b,0,sizeof(b));for(int i=1;i<=n;i++) {scanf("%d",&b[i].val);b[i].pos=i;}sort(b+1,b+n+1,lisanhua);for(int i=1;i<=n;i++) num[b[i].pos]=i;for(int i=1;i<=n;i++){add(num[i]);ans+=i-sum(num[i]);}printf("%lld\n",ans);ans=0;}return 0;
}