3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

(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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.