[Solved]: Difficulty in understanding an approach to SPOJ $d$-query problem

Problem Detail: 

I was trying to solve this problem on SPOJ:

Given a sequence of $n$ numbers $a_1, a_2, \ldots, a_n$ and a number of $d$-queries. A $d$-query is a pair $(i, j)$, $(1 \leq i \leq j \leq n)$. For each $d$-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a_i, a_{i+1}, \ldots, a_j$.

Specifically, the input to the problem is as follows.

• Line 1: $n$, where $1 \leq n \leq 30000$
• Line 2: $n$ numbers $a_1, a_2, \ldots, a_n$, where $1 \leq a_i \leq 10^6$
• Line 3: $q$, the number of $d$-queries, where $1 \leq q \leq 200000$
• Finally, $q$ lines, where each line contains 2 numbers $i, j$ representing a $d$-query, where $1 \leq i \leq j \leq n$.

But after a few hours of trying to solve it, I googled for a possible hint. I found one approach described here by user irancoldfusion:

First I thought a good O(n ^ 2 + q log q) would pass, but it didn't run in time. Then, I thought of the idea below which I haven't implemented yet:

The result of a query [a, b] is number of integers whose last occurrence in [1, b] is >= a.

Let's have two kinds of events: QueryEvent and NumberEvent. First we read whole input and sort all events, the key for QueryEvents are their end (i.e. b for query [a, b]), and for NumberEvents the key is their position in array.

We also have a segment tree which answers the queries of kind: how many elements are at position range [x, y]. Initially the tree is empty.

Then we process events in order: + When we meet a NumberEvent: 1. If number has occurred before at position p, we remove p from segment tree. 2. We add position of number to the segment tree. + When we meet a QueryEvent: - Query the segment tree, and find the answer.

The overall time complexity of algorithm is O( (n + q) log n + (n + q) log (n + q) )

But I am not able to understand it properly. Can anybody help me in understanding the approach. I want to understand how are the positions inserted and deleted from the tree. That is, what does the segment tree hold, say for an interval.

Asked By : Rahul Sharma

Answered By : D.W.

(This answer is no longer very interesting, now that the question has been corrected to clarify that $1 \le a_i \le 10^6$ instead of $1 \le a_i \le 106$.)

This can be solved in $10^6(n+q)$ operations.

First, build a table $T[\cdot,\cdot]$, where $T[j,x]$ is the index of the last occurrence of the number $x$ among $a_1,a_2,\dots,a_j$. In other words,

$$T[j,x] = \max \{i : a_i=x \wedge 1\le i\le j\}.$$

This table can be built in $10^6n$ steps.

Next, you should be able to see how to answer a query $(i,j)$ quickly, by doing some lookups into the $T$ table. I'll let you work out the details so you can have the fun of solving the problem.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14068