Given an array of N elements, answer Q queries asking if there exist two elements from two specified range with a given XOR value We have array of N (&lt;=10^5) elements with Q(&lt;=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".


Constraints:


1 &lt;= N &lt;= 10^5
1 &lt;= p,q,r,s &lt;= N
1 &lt;= A[i] &lt;= 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.

#include &lt;bits/stdc++.h&gt;
using namespace std;

typedef long long ll;
typedef vector&lt;int&gt; vi;
int a[100001];

bool query(int p,int q,int r,int s,int x)
{
    unordered_map&lt;int,int&gt; mp;
    for(int i =r;i&lt;=s;i++)
    {
        mp[a[i]]=1;
    }
    for(int i =p;i&lt;=q;i++)
    {
        if(mp.count(a[i]^x) &gt; 0)
        {
            return true;
        }
    }
    return false;
}

int main()
{
    int n,q;
    cin&gt;&gt;n&gt;&gt;q;
    for(int i =0;i&lt;n;i++)
    {
        cin&gt;&gt;a[i];
    }
    while(q--)
    {
        int p,q,r,s,x;
        cin&gt;&gt;p&gt;&gt;q&gt;&gt;r&gt;&gt;s&gt;&gt;x;
        // -1 because they are 1-indexed
        if(query(p-1,q-1,r-1,s-1,x))
        {
            cout&lt;&lt;"true\n";
        }
        else
        {
            cout&lt;&lt;"false\n";
        }
    }

    return 0;
}
Avoid non-standard headers. Especially giant composite-headers like &lt;bits/stdc++.h&gt;. They make your program unportable and/or  slow compilation down.
You are using using namespace std;.
That's a bad idea, read "Why is “using namespace std;” considered bad practice?".
Aside from its obscuring impact if you ever used the typedefs, vi and ll are unused. Remove to minimize confusion.
Do you know std::unordered_set? That's better for representing a set than std::unordered_map...
Anyway, you should change the algorithm but we'll get there later.
You should consider whether swapping the ranges can speed things up.
The conditional operator (ternary operator, exp ? true_exp : false_epp) is perfect for choosing the value to use.
You never check for input-failure or inputs being out-of-range.


Now the algorithm:

Consider initializing a std::unordered_multimap, or if duplicates are plentiful a std::unordered_map of sorted std::vector from the input-array.
Then for each query check every element in the smaller range whether element xor x is in the whole array, and filter that down to the second range.