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.

Topics we are covering

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("%lldn", 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 privet7

const 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("%lldn", countLess(r + 1) - countLess(l));
    }
}

int main() {
    int tc;
    scanf("%d", &tc);
    ensureLimit(tc, 1, 10);
    while (tc--) {
        solve();
    }
}

coding problems solutions