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
Offline solution: BIT + map. Online solution: treap, splay tree or sqrt descomposition.
How would you solve it with sqrt decomposition?
Split and rebuild style
Can you please explain what do you mean by 'offline' and 'online' solutions ?
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.
It can also be solved online with dynamic segment tree, with complexity O(QlogY)
cool..., the core idea of Li Chao Tree.