This is an \(O(n+q)\) solution.

First, it’s obvious that for each \(x=1,2,\cdots,n\), the \(y\) such that the answer to query \(x,y\) is Yes is a certain range \([l_x,r_x]\).Now let’s consider how to calculate \([l_x,r_x]\).

For each \(i=1,2,\cdots,n\), let \(p_i=\min\{j|b_j=a_i\}\) and \(q_i=\min\{j|a_j=a_i\}\), that is, the first appearance of \(a_i\) in \(b[1\cdots n]\) and \(a[1\cdots n]\). This can be calculated using some kind of hashmap.

Let \(S_i\) be the set of \(q_1,q_2,\cdots,q_n\), it’s easy to find that

\[ l_i=\max_{t\in S_i}p_t,r_i=\min_{t\in S_n-S_i}p_t-1 \]

Here \(S-T\) means the set \(\{u|u\in S,u\not\in T\}\).

By calculating the prefix maximum value and suffix minimum value of \(q\), we can find \(l_1,r_1,\cdots,l_n,r_n\) in \(O(n)\) time. Now we just need \(O(1)\) time to answer each question.

Be careful when implementing this solution. For example, for those \(i\) such that \(a_i\) does not appear in \(b\), we should set \(p_i=n+1\).

This Code uses \(O(n\log n)\) hash at first so the complexity is \(O(n\log n)\).It’s easy to optimize it to \(O(n)\) by using unordered_map or some other hashmaps.