I have been trying to understand this code, but still don't get the idea of the implementation.
The question that I am interested in is: Given an integer array, answer queries of the form (li, ri) by returning the number of distinct integers in that subarray. The code that I posted is a solution to the stated problem, plus an additional condition, but I only care for this subproblem.
I thought of an offline solution that answers queries in log n time each — Process each integer value in the array, and create a new interval for each pair of equal value integers that are "close" to one another. E.g. [1,x,x,1,x,1], x != 1 -> when I am processing the value 1, I will create two intervals (0,3), (3,5) Then, the answer to each query is the (ri-li+1) — number of intervals that are within (li, ri)
I could only think of an offline solution to this modified problem using BIT.
The solution from the code seems to handle the queries online. Can anybody help me understand the code?