Check if two separate ranges have some number in common

Question

We are given two permutations: A of size N and B of size M. We need to process Q queries, each query is given by two ranges, one subarray range in permutation A and one in B. We should check if there is at least one same number in those two ranges.

We don't need to answer the queries online, so we can sort them in different ways.

I tried different things with segment trees, but I don't have working ideas

Answer 1

You can get $\tilde{O}(NM)$ preprocessing time and $O(1)$ time per query.

Assume for simplicity that $N$ and $M$ are powers of $2$. For each index $i = 1, \dots, n$ and $h = 2^0, 2^1, \dots, 2^{\log N}$, let $A[i, h]$ be the set of the elements in positions from $i$ to $i + 2^h -1$ in $A$. Define $B[j, k]$ similarly.

Let $R[i, h, j, k]$ be true if $A[i,h] \cap B[j, k] \neq \emptyset$ and false otherwise. You can compute each $R[i, h, j, k]$ in constant time by exploiting the following relations: $$ R[i, h, j, k] = R[i, h-1, j, k] \vee R[i + 2^{h-1}, h-1, j, k] \quad \mbox{for }h>0 \\ R[i, h, j, k] = R[i, h, j, k-1] \vee R[i, h, j + 2^{k-1}, k-1] \quad \mbox{for }k>0$$

where $R[i, 0, j, 0]$ is true iff the i-th element of $A$ equals the $j$-th element of B.

There is an intersection between the elements of A in positions $i, i+1, \dots, i+\ell_A - 1$ and the elements of B in positions $j, j+1, \dots, j+ \ell_B - 1$ iff the following condition is true: $$ R[i, h, j, k] \vee R[i + h, h, j, k] \vee R[i, h, j + k, k] \vee R[i + h, h, j + k, k], $$ where $h = \lfloor \log \ell_A \rfloor$ and $k = \lfloor \log \ell_B \rfloor$.

Answer 2

Either I'm misunderstanding something or you're severely overcomplicating the issue.

Memory: N+2M

Runtime: Q*range_A

A: plain old array

B: hashmap value => position

For slice of A: If B.get(a) within range_B return true

Else return false