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


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

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