UVA 1428 - Ping pong ( BIT )

UVa Online Judge
For each candidate of umpire, the number of matches that can be held is
n( contestants in left ) with value lower than umpire's value * n( contestants in right ) with value higher +
n( contestants in left ) with value higher than umpire's value * n( contestants in right ) with value lower
So basically we will need to preprocess the number of contestants with lower value on both left and right sides, for each umpire candidate. It can be implemented with BIT, scanning from left to right while maintaining the prefix sum of count of value.

typedef long long ll;
typedef vector< int > vi;

struct BIT{
    vi dat;
    BIT( int sz ){
        dat.resize( sz );
        fill( dat.begin(), dat.end(), 0 );
    }
    void update( int x, int v ){
        for( int i = x; i < dat.size(); i += i & -i )
            dat[ i ] += v;
    }
    int qsum( int x ){
        int res = 0;
        for( int i = x; i > 0; i -= i & -i )
            res += dat[ i ];
        return res;
    }
};

void solve(){
    int N; cin >> N;
    vi A( N );
    for( int i = 0; i < N; ++i )
        cin >> A[ i ];

    BIT bit = BIT( 100001 );
    vi l_small_cnt( N ), r_small_cnt( N );
    for( int i = 0; i < N; ++i )
        l_small_cnt[ i ] = bit.qsum( A[ i ] ),
        bit.update( A[ i ], 1 );
    bit = BIT( 100001 );
    for( int i = N - 1; i >= 0; --i )
        r_small_cnt[ i ] = bit.qsum( A[ i ] ),
        bit.update( A[ i ], 1 );

    ll ans = 0;
    for( int i = 0; i < N; ++i )
        ans += 1LL * l_small_cnt[ i ] * ( N - i - 1 - r_small_cnt[ i ] )
            +  1LL * r_small_cnt[ i ] * ( i - l_small_cnt[ i ] );

    cout << ans << "\n";
}