Hamlet_Jr's blog

distinct element
By Hamlet_Jr, history, 6 years ago, In English

Say for , there is an array with 10^5 size. & there are 10^5 query.

In each query, there is given a range L-R .

within this range(inclusive) i want to find out how many distinct element remaining there??

Note: array elements are unsorted and any digit may occur frequently.

ex: 3 4 1 1 3 7 10

here if L=3,R=6 then the answer will be 3 because(distinct element within index 3 to 6 is 1,3,7)

i could do this using set if there only one query . but how can i do this if there 10^5 query within time limit 1s,2s or 3s .

thanks for advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Same as this problem: DQUERY You can do it with Mo's algorithm or Persistent Segment Tree. Also you can do this.

To solve it with Persistent Segment Tree you can store for each number the position of the next occurrence of this number in an array nxt, and then for each query (l, r) you can find the number of elements in nxt which are greater than r in the interval.

→ Reply