I’m trying to solve a question where I am given an array of n integers [a_1,\ldots,a_n], 1\le a_i\le n and multiple queries of the form i, j, k, l.

Each query wants the answer to the question:

Is the **set** of distinct elements in the subarray [a_i, \ldots, a_j] equal to the **set** of elements in [a_k,\ldots,a_l]

I want each query to be answered fast, in something like O(\log n), O(\log^2 n).

I have been trying a lot of different techniques, including segment trees, polynomial hashing but none of them are working for me.

Can anyone see a solution to this problem? The problem is the Subarray Set problem from here

EDIT: So I managed to get a solution using square root decomposition and hashing which answers each query in O(\sqrt{n}).

But I am still curious if this can be done faster…