HackerEarth XOR in Sequence problem solution

In this HackerEarth XOR in Sequence problem, we have given a sequence A consisting of N integer elements: A1, A2, .., AN.

Your task is to answer Q queries. Each query requires to count the number of pairs of integers (i, j) such that 1 ≤ i ≤ j ≤ N, and L ≤ Ai XOR Ai + 1 XOR Ai + 2 XOR ... XOR Aj ≤ R where L and R are given.

HackerEarth XOR in Sequence problem solution.

`#include <bits/stdc++.h>using namespace std;const int MAXN = 100000 + 10;const int MAXQ = 100 + 10;int a[MAXN];int n, q;vector<int> bits[2 * MAXQ];struct trie {    int c;    trie* next[2];    trie(int _c) {        c = _c;        next[0] = next[1] = NULL;    }};trie* root;int get_bit(int j, int i) {    return (i >> (j - 1)) & 1;}vector<int> analys(int x) {    vector<int> res(30);    for(int i = 1; i <= 30; i++) res[30 - i] = get_bit(i, x);    return res;}int calc(vector<int> &a, vector<int> &b) {    trie* curr = root;    int res = 0;    for(int i = 0; i < 30; i++) {        int j = a[i] ^ b[i], k = a[i] ^ (1 - j);        if ((k < b[i]) && (curr->next[1 - j] != NULL)) res += curr->next[1 - j]->c;        if (curr->next[j] == NULL) break;        curr = curr->next[j];    }    return res;}void push(vector<int> &a) {    trie* curr = root;    for(int i = 0; i < 30; i++) {        if (curr->next[a[i]] == NULL) curr->next[a[i]] = new trie(1);        else curr->next[a[i]]->c++;        curr = curr->next[a[i]];    }}int main(){    int test;    cin >> test;    assert((1 <= test) && (test <= 10));    while (test --) {        cin >> n;        assert((1 <= n) && (n <= 100000));        for(int i = 1; i <= n; i++) {            scanf("%d", &a[i]);            assert((1 <= a[i]) && (a[i] <= 1000000000));        }        cin >> q;        assert((1 <= q) && (q <= 10));        vector<int> b;        for(int i = 0; i < q; i++) {            int l, r;            cin >> l >> r;            assert((0 <= l) && (l <= r) && (r <= 1000000000));            b.push_back(l); b.push_back(r + 1);        }        for(int i = 0; i < b.size(); i++) bits[i] = analys(b[i]);        vector<long long> S(b.size());        root = new trie(0);        vector<int> c = analys(0);        push(c);        int sum_xor = 0;        for(int i = 1; i <= n; i++) {            sum_xor ^= a[i];            c = analys(sum_xor);            for(int i = 0; i < b.size(); i++) S[i] += calc(c, bits[i]);            push(c);        }        for(int i = 0; i < q; i++) printf("%lld\n", S[i * 2 + 1] - S[i * 2]); //cout << S[i * 2 + 1] - S[i * 2] << endl;    }}`

Second solution

`#include <algorithm>#include <memory.h>#include <cstdio>#include <iostream>#include <cmath>#include <string>#include <cassert>#include <map>#include <set>#include <vector>#include <queue>using namespace std;#define prev privet1#define next privet2#define y1 privet3#define rank privet4#define left privet5#define right privet6#define y0 privet7const double pi = 3.141592653589793238;void ensureLimit(long long n, long long l, long long r) {    assert(l <= n && n <= r);}const int MAX_N = 100333;int n, cnt;int a[MAX_N];int trie[2][MAX_N * 30], subtreeSize[MAX_N * 30];void add(int x) {    int v = 1, bit;    for (int i = 29; i >= 0; i--) {        if (x & (1 << i)) {            bit = 1;        }        else {            bit = 0;        }        if (trie[bit][v] == 0) {            cnt++;            trie[bit][v] = cnt;        }        subtreeSize[trie[bit][v]]++;        v = trie[bit][v];    }}int count(int x, int m) {    int v = 1, bitx, bitm, res = 0;    for (int i = 29; i >= 0; i--) {        if (x & (1 << i)) {            bitx = 1;        }        else {            bitx = 0;        }        if (m & (1 << i)) {            bitm = 1;        }        else {            bitm = 0;        }        if (bitx == 0 && bitm == 0) {            if (trie[0][v] == 0) {                return res;            }            v = trie[0][v];        }        else if (bitx == 1 && bitm == 0) {            if (trie[1][v] == 0) {                return res;            }            v = trie[1][v];        }        else if (bitx == 0 && bitm == 1) {            res += subtreeSize[trie[0][v]];            if (trie[1][v] == 0) {                return res;            }            v = trie[1][v];        }        else {            res += subtreeSize[trie[1][v]];            if (trie[0][v] == 0) {                return res;            }            v = trie[0][v];        }    }    return res;}long long countLess(int m) {    memset(trie, 0, sizeof(trie));    memset(subtreeSize, 0, sizeof(subtreeSize));    cnt = 1;    int tmp = 0;    long long res = 0;    add(0);    for (int i = 1; i <= n; i++) {        tmp ^= a[i];        res += count(tmp, m);        add(tmp);    }    return res;}void solve() {    scanf("%d", &n);    ensureLimit(n, 1, 100000);    for (int i = 1; i <= n; i++) {        scanf("%d", &a[i]);        ensureLimit(a[i], 1, 1000000000);    }    int queries;    scanf("%d", &queries);    ensureLimit(queries, 1, 10);    while (queries--) {        int l, r;        scanf("%d%d", &l, &r);        ensureLimit(l, 0, r);        ensureLimit(r, l, 1000000000);        printf("%lld\n", countLess(r + 1) - countLess(l));    }}int main() {    int tc;    scanf("%d", &tc);    ensureLimit(tc, 1, 10);    while (tc--) {        solve();    }}`