Fundamental Idea

Let \(S_A\) be the set of values contained in the first \(x_i\) terms of \(A\), and \(S_B\) be that of first \(y_i\) terms of \(B\). If \(|S_A| \neq |S_B|\), then the answer is obviously No. Therefore, the problem can be solved by determine if \(|S_A| \neq |S_B|\) and if \(S_A\) and \(S_B\) coincide when \(|S_A| = |S_B|\).

Precalculation 1

First, let \(S\) be a data structure like “set” in C++. For \(i=1,2,...,N\), insert \(a_i\) to \(S\) and record the size of \(S\) to a variable, and you can precalculate the size of the set of values contained in the first \(i\) terms of \(A\). We can do so for \(B\) too. Now we know the values of \(|S_A|, |S_B|\), and thus determine if \(|S_A| \neq |S_B|\). As described before, if \(|S_A| \neq |S_B|\) then the answer is No, so all that left is to process the case where \(|S_A|=|S_B|\).

Precalculation 2

Let \(a_i'\) be the \(i\)-th value to be added to \(S\) (as a new element of \(S\)) in Precalculation 1. We define \(b_i'\) for \(B\) in the same way. If we can determine for \(k=1,2,...\) if \(\{a_1', \ldots, a_k'\}\) and \(\{b_1', \ldots, b_k'\}\) are equal, then we can answer the query by letting \(k=|S_A|=|S_B|\).
In order to do so, again prepare a set-like data structure \(S\) and perform the following steps for \(k=1,2,...\).

• If \(S\) does not contain \(a_k'\), insert \(a_k'\); if it does, remove it.
• If \(S\) does not contain \(b_k'\), insert \(b_k'\); if it does, remove it.
• If \(|S|=0\), then \(\{a_1', \ldots, a_k'\}\) and \(\{b_1', \ldots, b_k'\}\) are equal; if not, they are not.

By inserting values if \(S\) does not contain the value, and removing it if it does, each value is contained in \(S\) if it is contained in exactly one of \(\{a_1', \ldots, a_k'\}\) and \(\{b_1', \ldots, b_k'\}\); if it is contained in both of or neither of them, it is not contained in \(S\). Therefore, \(\{a_1', \ldots, a_k'\}\) and \(\{b_1', \ldots, b_k'\}\) coincide if and only if \(S\) is empty.
The time complexity of this solution is \(\mathrm{O}(N\log N)\).

Another Solution (+Bonus)

This problem can alternatively be solved with Zobrist Hash, which is a probabilistic algorithm to determine if two sets are equal.
Also, together with data structures like segment tree that enable value update and segment XOR, we can solve the problem in the following form too.

• Determine if the set of values contained in \(a_{x_i}, a_{x_i+1} \ldots, a_{y_i}\) and that in \(b_{z_i}, b_{z_i+1} \ldots, b_{w_i}\) are equal.