Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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
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$.
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
