Omega1's blog

Distinct numbers on an interval
By Omega1, history, 11 years ago, In English

I have a question , need fast to do to two types of operations:

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 problem,can someone help me??

  • Vote: I like it
  • +10
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

Where is this problem from?

→ Reply
»
11 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

You can solve this problem with segment trees where each node of your segment tree is a set.

→ Reply
  • »
    »
    11 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +3 Vote: I do not like it

    Won't be fast enough. it will be O(N*logN) for merging nodes (the sets).

    So then range query will be answered in O(logN*logN*N). Also the building of the tree will be O(N*N*log(N)).

    → Reply
»
11 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

take new array.for each element of first array find next index where same element stand,if it is,else use value INF. for query l,r you should answer question: how many elements is greater than r in range (l,r) in new array? it is standart segment tree or other data structure problem,and can be solved in O(n * logn) .for update operation you should change next and previus values of modified element.

→ Reply
»
11 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

MO's algorithm. Since you're not updating the array, offline solution is possible. However, this has n*(sqrt(n)) complexity.

→ Reply