Distinct numbers on an interval

general
,
1

Given two type of queries
update: 1 x y element on position x become y;

query : 2 x y number of distinct numbers from the interval [ x , y ];

How to solve this using segment tree ,what to store in the nodes and how to merge two nodes ?

Can anyone describe their approach?

PS: I have read the comments but did not understand it.

Link:Distinct numbers on an interval - Codeforces

2

Ohk so lets talk abt the logic to solve
this.

Lets say arr is [3,4,4,3,4]

I want to know the ans for range[1,4]

Lets create a nxt[] which contains index of nxt occurence,if no occurrence after,then nxt[i]=6 lets say

So nxt[]=[4,2,5,6,6]

So ans for range [1,4] is no.of elements greater than 4(ie r)

Reason?-> lets say 2 sane elements occur in range(1,4) ,obviously the first of them will have nxt less than r(since the next element is in the range),2nd element will have nxt greater than r.

Now question reduces to how to find no.of elements greater than r in range[l,r].

For handling updates u can simply store the indices of elements in vector.

Ie for 3 4 4 3 4

Arr[3]->1,4

Arr[4]->2,3,5

So now u can easily update(just change the prev element nxt and this element nxt accordingly )

Now coming back to og question,no.of elements greater than r,

1)sqrt decomposition

Divide the array into sqrt blocks ,sort each block,then just binary search for r in each block to find no.of elements greater than r

Complexity:-O(Qroot(N)logN)

2)segment tree with ordered set in each node

Lets say each node consists of ordered set of the range.So u can simply binary search and find no.of elements greater than r
,see this for ordered set:-

https://discuss.codechef.com/questions/124050/stl-binary-search

Complexity:-O(Qlog^n)

3)segment tree with each node having a dynamic segment tree

This is similar to the above method.One can have a dynamic segment tree in each node,where that DST[range] gives no.of elements in range.

Complexity:O(nlog^2)

Just in case if no update were there u could do :-

Wavelet tree ( link:- Introduction to New Data Structure: Wavelet Trees - Codeforces)

I dont know if update can be done on this

Complexity:O(qlogN)

5)persistent segment tree

Build a persistent segmnet tree such that seg[i:j] gives count of number of elements(values not indices) in (i,j).

So to ans (l,r) :- rthseg[r+1,inf] - (l-1)thseg[r+1,inf]

(Xthseg[i,j] denite no.of elements with values in range(i,j) and indices (1,X))

Complexity :- O(qlogn)

And last method :slight_smile:

6)simple segment tree

See to answer (l,r) if we know no.of elements in range[1,r] and [1,l-1] greater than r,then ans is simply difference of the two

So just process the queries lyk,lets say we have queries :-

(3,5)

(2,4)

So i have to calculate (i,j) which denote no.of elements greater than j in range[1,i]

I mean we have to calculate (2,5),(5,5),(1,4),(4,4)

Now sort these values in decreasing order based on first value

(5,5),(4,4),(2,5),(1,5)

Now lets say we have a segment tree where seg[range] returns no.of elements in range.

So to ans (i,j) we need to have a segment tree of first i elements and query for range[j+1,inf]

So as we process it backwards we can easily process all queries(ie first u have seg tree for first 5 elements ,so if want for 4 elements delete the 5th element)

Complexity :- O(qlogn)
Sorry if my comment is too large,i’ ve written it just in case if any1 else wanna know.:slight_smile:

(And yeah if A[i] is large u can use cordinate compression(which is basically mapping them to small values after sorting))

19 Likes
3

Can you give the link of the problem statement or maybe constraints on A[i]?

4

@dishant_18 question is in the above mentioned link and and the constraints are quite obvious i.e N and Q are in the range of 100000 and A[i] can be upto 10^9

5

Simply wonderful!!!

6
1 Like
7

thanks sir learned a new concept :slight_smile:

8

this can only be done if the values are small

9

I generally like to know why an algorithm exists. So… why have we created a next[] array? IMO it’s just a way to consider only the last appearance of each element inside a range.

Example - array is [1, 2, 3, 1, 4] and query [1, 5].
Given that - all duplicate elements within a range [L, R] must have its next[] <= R.
Even though element 1 appears twice in the range, only the 2nd appearance has next[] > R, so we can ignore all appearances but the last one!

Also, we could use a 2D data structure to store these values as well. Let’s consider the array index as the X coordinate. Y coordinate is their next[] value.
We can make queries in a rectangle shape by considering the query range on X axis and looking up to values starting from its range limit.

Example (0-index based):

  • Array: [3, 2, 4, 2, 3]
  • Nxt: [4, 3, 5, 5, 5]

Which is:

  • update index (0, 4) with 3
  • update index (1, 3) with 2
  • update index (2, 5) with 5
  • update index (3, 5) with 2
  • update index (4, 5) with 3

Query:

  • [1, 3] → rectangle X: (1, 3), Y: (4, infinite)
    • You can see that element 2 is inside X range but outside of Y range, so it will be ignored