If you have not seen already, DQUERY is a problem on SPOJ which asks us to query the number of distinct elements present in a range.

There are ways to solve it online, which might also be possible with what I'll be discussing today, but for sake of explanation we'll solve it offline.

Offline way to solve DQUERY involves use of Fenwick Trees, which is already a well-known technique but we'll try to formulate the solution ourselves in a much more intuitive way.

Let us forget about queries, assume we've a hypothetical $$$N \times N$$$ grid $$$distinct$$$ where $$$distinct[i][j]$$$ is the number of distinct elements present in subarray $$$A[i,j]$$$.

Now we'll use the technique of individual contribution, ie. rather than taking a range and counting distinct, we take an element and find all ranges where this element will contribute an answer to, In order to do that we need a way to resolve duplicates, ie. if there are duplicates only first occurrence should be counted, this makes it very easy to avoid overcounting.

An element $$$A[i]$$$ contributes to all subarrays where it is first occurrence of itself, ie. any subarray which starts after previous occurrence of $$$A[i]$$$ and contains index $$$i$$$.

If we try to increment contribution of $$$A[i]$$$ in our hypothetical $$$distinct$$$ grid, we see that each cell $$$distinct[x][y]$$$ where $$$prev[arr[i]] + 1 \le x \le i$$$ and $$$i \le y \le N - 1$$$