CFR 703 D. Mishka and Interesting sum ( XOR, BIT )

Problem - D - Codeforces
This is actually a good problem. While as always xor-sum will give us only the xor-sum of the values that appeared odd number of times in the range, we have to find the xor-sum of each number that appeared even number of times instead. Somehow we will come up to that we have to find the xor-sum of distinct values in the range, and apply it with xor to the usual xor-sum, to hold a result as the answer. The problem now becomes how we should find xor-sum of distinct elements in any given range. It would be quite instinctive to think of Mo's algorithm, however, it is too slow for the length of the range goes as much to a million. So we will have to think in another fashion. Consider dealing each query with its right bound fixed, we will try to maintain the distinct-value-xor-sum as we move. In order to implement that, we will need to record the last position of each value. We will have prefixes that only are xor-sums of values that do not appear in the rest of the current range, and with that, the prefixes will have the xor-sum property that leads to finding the distinct-value-xor-sum of range [ i, r ] for any i. When the right bound is extended, if the new element inserted in appears to be some value that has been inserted before, simply nullify the last one ( apply again with xor and will be 0 ), and wear the effects on the new one. Therefore it is clear that we will need Fenwick tree for these operations.

struct BIT{
    vi dat;
    BIT( int _sz ){
        dat.resize( _sz + 1 );
        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 sum( 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 ];

    vi prefix_xor( N + 1 );
    for( int i = 0; i < N; ++i )
        prefix_xor[ i + 1 ] = prefix_xor[ i ] ^ A[ i ];

    int M; cin >> M;
    vector< vector< pii > > query( N + 1 );
    for( int i = 0; i < M; ++i ){
        int ql, qr; cin >> ql >> qr;
        query[ qr ].push_back( { ql, i } );
    }

    vi ans( M );

    BIT bit( N + 1 );
    map< int, int > last_pos;
    for( int i = 1; i <= N; ++i ){
        if( last_pos.count( A[ i - 1 ] ) )
            bit.update( last_pos[ A[ i - 1 ] ], A[ i - 1 ] );
        last_pos[ A[ i - 1 ] ] = i;
        bit.update( i, A[ i - 1 ] );
        for( pii &q : query[ i ] )
            ans[ q.second ] = prefix_xor[ i ] ^ prefix_xor[ q.first - 1 ]
                            ^ bit.sum( i ) ^ bit.sum( q.first - 1 );
    }

    for( int i = 0; i < M; ++i )
        cout << ans[ i ] << "\n";
}