Return to Question

• 1 ≤ N ≤ 105
• 1 ≤ p,q,r,s ≤ N
• Ranges [p,q] and [r,s] do not overlap.
• 1 ≤ A[i] ≤ 105

• 1 ≤ N ≤ 105
• 1 ≤ p,q,r,s ≤ N
• 1 ≤ A[i] ≤ 105

We have array of N (<=10^5) elements with Q(<=10^5) queries.

Each query is of type: p q r s x, where we have to find if there exist a element from array in range [p,q] and an element in [r,s] whose xor is equal to X. If exists, print "true" else "false".

1 <= N <= 10^5
1 <= p,q,r,s <= N
Ranges [p,q] and [r,s] do not overlap.
1 <= A[i] <= 10^5
Example: 
Array : 1 2 3 4 5 6
Query : 1 3 4 6 5 
Output: true.

1 from range [1,3] and 4 from range [4,6] has an XOR value equal to X=5.

I tried to solve it by loading the second sub array into a hashmap then XORing x with each element from first array and if the result exists in hashmap answer is yes.

But this \$O(n)\$ solution for each query isn't sufficient to pass. I am looking for ideas for how I can achieve this in possible \$O(logn)\$ or \$O(1\$) time for each query, or if it is possible to answer queries offline using MO's algorithm in \$O(sqrt(n))\$ time.

We have array of N (≤105) elements with Q(≤105) queries.

Each query is of type: p q r s x, where we have to find if there exist a element from array in range [p,q] and an element in [r,s] whose xor is equal to X. If exists, print "true" else "false".

• 1 ≤ N ≤ 105
• 1 ≤ p,q,r,s ≤ N
• Ranges [p,q] and [r,s] do not overlap.
• 1 ≤ A[i] ≤ 105

Example:

• Array: 1 2 3 4 5 6
• Query: 1 3 4 6 5
• Output: true.

1 from range [1,3] and 4 from range [4,6] has an XOR value equal to X=5.

I tried to solve it by loading the second sub array into a hashmap then XORing x with each element from first array and if the result exists in hashmap answer is yes.

But this O(n) solution for each query isn't sufficient to pass. I am looking for ideas for how I can achieve this in possible O(log n) or O(1) time for each query, or if it is possible to answer queries offline using MO's algorithm in O(√n) time.