我是题目链接](http://poj.org/problem?id=2299) 设A为有n个数字的有序集(n>1)，其中所有数字各不相同。如果存在正整数i, j使得1 ≤iA[j]，则这个有序对称为A的一个逆序对，也称作逆序数。 在这个问题中，你需要快速的求出一个给定数组中逆序对的数量
Input 输入包含多个测试用例，每个测试用例第一行为一个整数n（n<500000）表示数组的长度，下面n行每一行包含一个整数0≤a[i]≤999,999,999，即数组中第i个元素的值。当n=0时结束输入 Output 对于输入的每个数组，程序应该输出该数组中逆序对的数量
Sample Input 5 9 1 0 5 4 3 1 2 3 0
Sample Output 6 0 解题思路： 树状数组可以以nlogn的时间复杂度求序列的逆序对；
//树状数组 #include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> using namespace std; #define MAX 500010 #define ll long long int c[MAX]; int aa[MAX]; int n; struct node{ int val; int order; }in[MAX];//结构体存入 int lowbit(int x)// { return x&(-x); } //void update(int x,int val)//修改 //{ // while(x<=n){ // c[x]+=val; // x+=lowbit(x); // } //} void update(int x,int val) { for(int j=x;j<=n;j+=lowbit(j)) { c[j]+=val; } } //int sum(int x) //{ // int s=0; // while(x>=1) // { // s+=c[x]; // x-=lowbit(x); // } // return s;//一开始竟然忘记写了这个语句，还以为树状数组写错了呢 //} int sum(int k)//求和 { int ans=0; for(int i=k;i>0;i-=lowbit(i)) { ans+=c[i]; } return ans; } bool cmp(node a,node b){ return a.val<b.val; } int main() { while(scanf("%d",&n)==1&&n){ for(int i=1;i<=n;++i) { scanf("%d",&in[i].val); in[i].order=i; } sort(in+1,in+n+1,cmp); for(int i=1;i<=n;++i) aa[in[i].order]=i;//离散化到小范围来 memset(c,0,sizeof(c)); ll ans=0; for(int i=1;i<=n;++i) { update(aa[i], 1); ans+=(i-sum(aa[i])); } cout<<ans<<endl; } return 0; }