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