Distinct elements in subarray using Mo’s Algorithm

Explanation

- **Mo’s Algorithm** is a square root decomposition technique for answering range queries efficiently. It is especially useful for problems where we need to find distinct elements in a subarray. The algorithm sorts the queries and processes them in a way that minimizes the movement of the window boundaries, resulting in efficient querying.

-

• Steps

  • Divide the array into blocks of size √n.
  • Sort the queries based on block number and the right endpoint of the range.
  • For each query, adjust the current window (move the left or right boundary) to match the range specified in the query while keeping track of the distinct elements.
  • Return the answer for each query after processing the range.

• Time Complexity:

  • O((n + q) * √n), where n is the length of the array and q is the number of queries.