POJ2299 [Ultra-QuickSort] 值域树状数组

题解：值域树状数组

值域树状数组就是以值域建树。比如，一个数是 x ， 那么我们建树的方法就是在x的地方加1.那么如何统计逆序对的个数呢？我们的方法就是插入每个数后，看在这个数之前插入的数中，有多少个数比它大，然后加入答案。

# define Name ""

# include <cstdio>
# include <cstring>
# include <iostream>
# include <algorithm>

# define LL long long

using 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 ;
}