farukshin's blog

How to implement the "Set value" operation in a Treap by an implicit key?
By farukshin, history, 3 years ago, In English

Can't figure out how to implement Set operation.

Everything is clear with the operations Add, Sum, Min, Reverse, Revolve, Insert, Delete

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am little confused about your query , by set operations do u mean union, intersection operations or normal unique value or just sorted nature or both sorted and unique.
Anyways see if this helps
https://mirror.codeforces.com/blog/entry/46507

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

    Thanks for the link

    e.g. task https://www.e-olymp.com/en/problems/2307

    But I wanted to understand — is it possible to solve using a Treap by an implicit key?

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

      Can you implement the same operation using segment tree nodes with lazy propagation if yes, you can do the same for treap nodes with log(n) amortized complexity or average I guess. Ping me if you need implementation link of the same.

      → Reply
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

why do you care?

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

Just split the treap around the value to be removed, insert a new treap with the new value and merge the three treaps.

→ Reply