题解：值域树状数组
值域树状数组就是以值域建树。比如，一个数是 x ， 那么我们建树的方法就是在x的地方加1.那么如何统计逆序对的个数呢？我们的方法就是插入每个数后，看在这个数之前插入的数中，有多少个数比它大，然后加入答案。
# define Name ""# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm># define LL long longusing namespace std ;const int N = 5e5 + 10 ;int a [N] , b [N] , c [N] , n ;int lowbit ( int x ) {return ( - x ) & x ;
}void modify ( int pos , int val ) {for ( int i = pos ; i <= n ; i += lowbit ( i ) ) c [i] += val ;
}int query ( int pos ) {int ret = 0 ;for ( int i = pos ; i >= 1 ; i -= lowbit ( i ) ) ret += c [i] ;return ret ;
}int main () {while ( scanf ( "%d" , & n ) != EOF && n ) {memset ( c , 0 , sizeof c ) ;for ( int i = 1 ; i <= n ; ++ i ) scanf ( "%d" , & a [i] ) , b [i] = a [i] ;sort ( a + 1 , a + 1 + n ) ;for ( int i = 1 ; i <= n ; ++ i ) b [i] = lower_bound ( a + 1 , a + 1 + n , b [i] ) - a ;LL ans = 0 ;for ( int i = 1 ; i <= n ; ++ i ) {modify ( b [i] , 1 ) ; ans += i - query ( b [i] ) ;}printf ( "%lld\n" , ans ) ; }return 0 ;
}