CF 617E XOR and Favorite Number ( Mo's Algorithm )

Problem - E - Codeforces
For a range query [ ql, qr ], we are asked to find the number of distinct pairs that XOR to a given number K. Since it is a range XOR problem, we will consider precomputing prefix XOR pa for the original array a. Now the problem transforms to counting the number of pairs ( i, j ) that satisfies
ql ≤ i ≤ j ≤ qr and pa[ j ] ^ pa[ i - 1 ] == k
Which we could switch to, find for all such j'th element, the count of elements in range x ∈ [ i - 1, j - 1 ] that satisfies pa[ j ] == pa[ x ] ^ k, and sum up count[ pa[ j ] ] * count[ pa[ j ] ^ k ]. Notice that when k == 0, we should sum up count[ pa[ j ] ] * ( count[ pa[ j ] ] - 1 ) / 2 instead.
We can update and query in O( 1 ) time going either left or right by 1 element, thus Mo's algorithm should be applied. O( ( n + m ) * sqrt( n ) ).
Notice that long long is needed. I was not having a clear mind and declared int cnt[ MAXK ]; which later on I had written += cnt[ x ] * cnt[ x ] and caused silly overflow.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXM = 1e5 + 5;
const int MAXK = 1e7 + 6;

int n, m, k;
ll a[MAXN], pa[MAXN];

struct Query{
    int ql, qr, id;
    ll ans;
    Query(){}
    void read(int _id){
        cin >> ql >> qr;
        id = _id;
    }
} qry[MAXM];

int blk[MAXN];
bool cmp_lr(const Query &a, const Query &b){
    if( blk[ a.ql ] != blk[ b.ql ] ) return blk[ a.ql ] < blk[ b.ql ];
    return a.qr < b.qr;
}
bool cmp_id(const Query &a, const Query &b){
    return a.id < b.id;
}

ll cnt[MAXK]; // forgot this = =, overflow happens for 1e6 * 1e6 before assigning
void solve(){
    int BLK_SIZE = sqrt( n ) + 1;
    for(int i = 1; i <= n; ++i)
        blk[ i ] = ( i - 1 ) / BLK_SIZE;
    sort( qry, qry + m, cmp_lr );

    int lb = 2, rb = 1; // [ lb, rb ]
    ll cur_ans = 0;
    for(int i = 0; i < m; ++i){
        while( rb < qry[ i ].qr ){
            ++rb;
            if( k == 0 ) cur_ans -= cnt[ pa[rb] ] * ( cnt[ pa[rb] ] - 1 ) / 2;
            else cur_ans -= cnt[ pa[rb] ] * cnt[ pa[rb] ^ k ];
            ++cnt[ pa[rb] ];
            if( k == 0 ) cur_ans += cnt[ pa[rb] ] * ( cnt[ pa[rb] ] - 1 ) / 2;
            else cur_ans += cnt[ pa[rb] ] * cnt[ pa[rb] ^ k ];
        }
        while( rb > qry[ i ].qr ){
            if( k == 0 ) cur_ans -= cnt[ pa[rb] ] * ( cnt[ pa[rb] ] - 1 ) / 2;
            else cur_ans -= cnt[ pa[rb] ] * cnt[ pa[rb] ^ k ];
            --cnt[ pa[rb] ];
            if( k == 0 ) cur_ans += cnt[ pa[rb] ] * ( cnt[ pa[rb] ] - 1 ) / 2;
            else cur_ans += cnt[ pa[rb] ] * cnt[ pa[rb] ^ k ];
            --rb;
        }
        while( lb > qry[ i ].ql - 1 ){
            --lb;
            if( k == 0 ) cur_ans -= cnt[ pa[lb] ] * ( cnt[ pa[lb] ] - 1 ) / 2;
            else cur_ans -= cnt[ pa[lb] ] * cnt[ pa[lb] ^ k ];
            ++cnt[ pa[lb] ];
            if( k == 0 ) cur_ans += cnt[ pa[lb] ] * ( cnt[ pa[lb] ] - 1 ) / 2;
            else cur_ans += cnt[ pa[lb] ] * cnt[ pa[lb] ^ k ];
        }
        while( lb < qry[ i ].ql - 1 ){
            if( k == 0 ) cur_ans -= cnt[ pa[lb] ] * ( cnt[ pa[lb] ] - 1 ) / 2;
            else cur_ans -= cnt[ pa[lb] ] * cnt[ pa[lb] ^ k ];
            --cnt[ pa[lb] ];
            if( k == 0 ) cur_ans += cnt[ pa[lb] ] * ( cnt[ pa[lb] ] - 1 ) / 2;
            else cur_ans += cnt[ pa[lb] ] * cnt[ pa[lb] ^ k ];
            ++lb;
        }
        qry[ i ].ans = cur_ans;
    }
    sort( qry, qry + m, cmp_id );
    for(int i = 0; i < m; ++i)
        cout << qry[ i ].ans << endl;
}

int main(){
    ios::sync_with_stdio( false );
    cin >> n >> m >> k;
    for(int i = 1; i <= n; ++i){
        cin >> a[ i ];
        pa[ i ] = pa[ i - 1 ] ^ a[ i ];
    }
    for(int i = 0; i < m; ++i)
        qry[ i ].read( i );
    solve();
    return 0;
}