Upgrading.....'s blog

Multiple queries Problem
By Upgrading....., history, 6 years ago, In English

You have an empty set. You have to support Q queries in the form —

1 X: Insert an element X in the set. It is guaranteed that X isn't already present in the set.

2 X: Delete an element X from the set. It is guaranteed that X is present in the set.

3 Y: Find and print sum of maximum Y elements in the set. If there are less than Y elements in the set, you need to print sum of all elements.

What is the best way to solve this problem? X<=10^9, Q<=10^5 Y<=10^5

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

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

Offline solution: BIT + map. Online solution: treap, splay tree or sqrt descomposition.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would you solve it with sqrt decomposition?

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please explain what do you mean by 'offline' and 'online' solutions ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      An "offline" solution needs to know all the queries beforehand to work efficiently (for example it might reorder the queries for faster answering). An "online" solution works efficiently even if it is given one query at a time.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    It can also be solved online with dynamic segment tree, with complexity O(QlogY)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      cool..., the core idea of Li Chao Tree.

      → Reply